八大排序——归并排序

1.基本思想

2.动态图

3.分解的时候我们可以使用递归的方式进行

代码解释

1. main 方法

2. mergeSort 方法

3. merge 方法

示例运行过程

初始数组

每轮排序后的数组

代码总结

合并两个有序序列

1.基本思想

归并排序就是递归得将原始数组递归对半分隔，直到不能再分（只剩下一个元素）后，开始从最小的数组向上归并排序。

将一个数组拆分为两个，从中间点拆开，通过递归操作来实现一层一层拆分。
从左右数组中选择小的元素放入到临时空间，并移动下标到下一位置。
重复步骤2直到某一下标达到尾部。
将另一序列剩下的所有元素依次放入临时空间。
将临时空间的数据依次放入原数据数组。

2.动态图

下边是动态图

3.分解的时候我们可以使用递归的方式进行

首先我们可以先定义三个变量，

数组的头部位置可以定义为 low，数组的尾部可以定义为high

因为每次分解都是要折半，所以我们可以定义数组的中间是 mid,如下图所示

我们从上图当中可以看到，我们每一次递归，都是将原来的mid当成新的high,一直到low = high的时候我们就已经可以说明我们将一个数据分离了出来。所以我们可以写以下代码来表示分。

   public static void mergeSort(int[] a, int low, int high) {
       //首先判断 low 和 high是否指向一个地方
       if(low >= high) {
           return;
       }
       int mid = (low + high)/2;
       //先递归左边
       mergeSort(a, low, mid);
       //在递归右边
       mergeSort(a, mid+1, high);

}

首先我们可以先递归左边，直到我们讲第一个值分离出去，然后再回溯，分离他右边的那个，如下如所以：

当递归完成之后我们该开始合并了

首先我们需要先弄懂一个地方就是合并是在哪里开始的。

首先我们要知道我们第一次回溯之后，将第二个元素分离了出来，第二个元素分离完成之后，也会回溯回去，那么此一次合并就是值 6 和 5的合并。

下边我们为了演示选择了 5，6 ， 1 ， 3的合并过程

首先我们需要弄清楚，我们这里所谓的分离其实是概念意义上的，在我们的数组结构上其实并没有分离，而且由于回溯的原因 5，6 ， 1 ， 3是其实和上边是对应的关系，如图所示

下边我们来一步一步的展示整个合并的过程，

首先我么可以定义两个指针，s1和s2,然后在定义一个新的临时数组来存储数据

我们将指针s1的范围锁定在 s1<=min ,将指针s2的范围锁定在s2<=high,我们可以比较s1和s2当前指向的值的大小，将小的一方放入到临时数组当中去，直到s1或s2一方指向为空，那么就可以将另一方全部放入到临时数组当中去。然后将临时的代码在放回数组

代码如下：

代码

public class ShellSort {
	
	public static void main(String[] args) {
        int a[] = {6,5,3,1,8,7,2,4};
        mergeSort(a, 0, a.length - 1);
        System.out.println("排序结果：" + Arrays.toString(a));
	}
	//分
	public static void mergeSort(int[] a, int low, int high) {
		//首先判断 low 和 high是否指向一个地方
           // 正常情况下就是 == 
		if(low == high) {
			return;
		}
		int mid = (low + high)/2;
		//先递归左边
		mergeSort(a, low, mid);
		//在递归右边
		mergeSort(a, mid+1, high);
		//合并
		merge(a,low,mid,high);
		System.out.println(Arrays.toString(a));
    }
	//合并
	public static void merge(int[] a, int low, int mid, int high) {
		//定义第一个段的开始
		int s1 = low;
		//定义第二个段的开始
		int s2 = mid+1;
		//定义临时数组
		int[] temp = new int[high-low+1];
		int i = 0;//定义临时数组的下标
		//判断大小将数组放入到临时数组当中去
		while(s1<=mid && s2<=high) {
			if(a[s1] <= a[s2]) {
				temp[i++] = a[s1++];
			}else {
				temp[i++] = a[s2++];
			}
		}
		//判断s1当中是否有数据，如果有将其全部拷贝到临死数组当中去
		while (s1 <= mid) {
			temp[i++] = a[s1++];
			
		}
		
		//判断s1当中是否有数据，如果有将其全部拷贝到临死数组当中去
		while (s2 <= high) {
			temp[i++] = a[s2++];
			
		}
		
		//将临时数组当中的代码放回原数组
		for (int j = 0; j < temp.length; j++) {
			a[j+low] = temp[j];
		}
		
	}
}

代码解释

1. `main` 方法

public static void main(String[] args) {
    int a[] = {6, 5, 3, 1, 8, 7, 2, 4};
    mergeSort(a, 0, a.length - 1);
    System.out.println("排序结果：" + Arrays.toString(a));
}

功能：程序的入口。
逻辑：
- 定义了一个未排序的整数数组 a。
- 调用 mergeSort 方法对数组进行排序。
- 打印排序后的数组。

2. `mergeSort` 方法

public static void mergeSort(int[] a, int low, int high) {
// 首先判断 low 和 high 是否指向一个地方
if (low == high) {
return;
}
int mid = (low + high) / 2;
// 先递归左边
mergeSort(a, low, mid);
// 再递归右边
mergeSort(a, mid + 1, high);
// 合并
merge(a, low, mid, high);
System.out.println(Arrays.toString(a));
}

功能：实现归并排序的分治逻辑。
逻辑：
1. 递归终止条件：
  - 如果 low == high，说明当前子数组只有一个元素，无需排序，直接返回。
2. 计算中间位置：
  - mid = (low + high) / 2，将数组分成两个子数组。
3. 递归排序左半部分：
  - 调用 mergeSort(a, low, mid)，对左半部分进行排序。
4. 递归排序右半部分：
  - 调用 mergeSort(a, mid + 1, high)，对右半部分进行排序。
5. 合并两个有序子数组：
  - 调用 merge(a, low, mid, high)，将两个有序子数组合并成一个有序数组。
6. 打印每轮排序后的数组：
  - 每轮排序后，打印当前数组的状态。

3. `merge` 方法

public static void merge(int[] a, int low, int mid, int high) {
// 定义第一个段的开始
int s1 = low;
// 定义第二个段的开始
int s2 = mid + 1;
// 定义临时数组
int[] temp = new int[high - low + 1];
int i = 0; // 定义临时数组的下标
// 判断大小将数组放入到临时数组当中去
while (s1 <= mid && s2 <= high) {
if (a[s1] <= a[s2]) {
temp[i++] = a[s1++];
} else {
temp[i++] = a[s2++];
}
}
// 判断 s1 当中是否有数据，如果有将其全部拷贝到临时数组当中去
while (s1 <= mid) {
temp[i++] = a[s1++];
}
// 判断 s2 当中是否有数据，如果有将其全部拷贝到临时数组当中去
while (s2 <= high) {
temp[i++] = a[s2++];
}
// 将临时数组当中的数据放回原数组
for (int j = 0; j < temp.length; j++) {
a[j + low] = temp[j];
}
}

功能：合并两个有序子数组。
逻辑：
1. 初始化指针：
  - s1 指向左半部分的起始位置（low）。
  - s2 指向右半部分的起始位置（mid + 1）。
2. 定义临时数组：
  - temp 用于存储合并后的有序数组。
3. 比较并合并：
  - 比较 a[s1] 和 a[s2]，将较小的元素放入 temp 中。
  - 移动相应的指针（s1 或 s2）。
4. 处理剩余元素：
  - 如果左半部分还有剩余元素，将其全部拷贝到 temp 中。
  - 如果右半部分还有剩余元素，将其全部拷贝到 temp 中。
5. 将临时数组的数据拷贝回原数组：
  - 将 temp 中的数据拷贝回原数组 a 的对应位置。

示例运行过程

初始数组

[6, 5, 3, 1, 8, 7, 2, 4]

每轮排序后的数组

第1轮：
- 左半部分排序：[5, 6]
- 右半部分排序：[1, 3]
- 合并结果：[1, 3, 5, 6, 8, 7, 2, 4]
第2轮：
- 左半部分排序：[1, 3, 5, 6]
- 右半部分排序：[2, 4, 7, 8]
- 合并结果：[1, 2, 3, 4, 5, 6, 7, 8]