归并排序采用经典的分治策略,利用归并的思想实现的排序方法。把一个待排序的数组无限拆分,直到子数组只有一个元素,然后开始按顺序再进行合并。想象一下若一副扑克牌乱序混在一起,如何从小到大排序?

  1. 把牌堆分层两份,分给两个小伙伴进行从小到大排序。
  2. 两位小伙伴排序完成,给到有序牌堆A和有序牌堆B。
  3. 每次抽取两个牌堆最顶端一张进行比较,较小的合入到整体有序的牌堆C中。

那么两个小伙伴是如何把分到的扑克牌给排序完成的呢?

  1. 把牌堆分层两份,分给两个小伙伴进行从小到大排序。

  2. 两位小伙伴排序完成,给到有序牌堆A和有序牌堆B。

  3. 每次抽取两个牌堆最顶端一张进行比较,较小的合入到整体有序的牌堆C中。

那么两个小伙伴是如何把分到的扑克牌给排序完成的呢?

重复步骤1-3 ···

当某次分牌时,某两位小伙伴各自仅分到了一张牌,那就不能再继续分了,他俩把分到的牌按照大小顺序交上去,这样就有了有序的牌堆(2张牌),然后2张合4张,4张合8张···,到最后整副扑克牌都是有序的。

这就是归并的思想

MergeSrot

动图理解:

2346780

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* @param arr 带排序的数组
* @param low 数组中较低的一侧的下标
* @param high 数组中较高的一侧的下标
*/
public static void mergeSort(int[] arr, int low, int high) {
int middle = (high + low) / 2;
if (low < high) {
// 处理左边
mergeSort(arr, low, middle);
// 处理右边
mergeSort(arr, middle + 1, high);
// 合并左右两边
merge(arr, low, middle, high);
}
}

/**
* @param arr 待归并的数组
* @param low 左侧数组起始位置
* @param middle 左侧数组的结束位置
* @param high 右侧数组结束位置
*/
private static void merge(int[] arr, int low, int middle, int high) {
// 用于存储归并后的临时数组
int[] temp = new int[high - low + 1];
// 记录第一个数组中需要遍历的下标
int i = low;
// 记录第二个数组中需要遍历的下标
int j = middle + 1;
// 用于记录在临时数组中存放的下标
int index = 0;
while (i <= middle && j <= high) {
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
// 一个数组中的数已经全部放入temp,剩下较长的一个子数组的数全部放进temp中
while (j <= high) {
temp[index++] = arr[j++];
}
while (i <= middle) {
temp[index++] = arr[i++];
}
// 把临时数组中的数据重新存入原来数组
for (int k = 0; k < temp.length; k++) {
arr[k + low] = temp[k];
}
}