归并排序通过对数组进行二叉树式的拆分最后再合并,完成了其排序过程,并将时间复杂度下降到了 O(nlogn) 的程度,下面是一个数组索引 0 - 9 的数组的拆分的过程

归并拆分过程

 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
    public static void mergerSort(int[] array, int low, int high) {
        // 观察上图可以发现,最终拆分的结果都是 low == high
        if (low == high) return;
        // 计算中间值
        int mid = (low + high) / 2;
        // 先递归拆左边
        mergerSort(array, low, mid);
        // 再递归拆右边,右边从 mid + 1 开始
        // 区间范围是 [mid+1, high]
        mergerSort(array, mid + 1, high);
        // 最终合并,合并的时间和二叉树后序遍历节点的顺序一致
        mergerArray(array, low, mid, high);
    }

    private static void mergerArray(int[] array, int low, int mid, int high) {
        // 合并的思路是先将数组放到一个排好序的临时数组
        // 然后再将临时数组中的数据拷贝回原数组
        int[] tmpArray = new int[high - low + 1];
        int tmpArrayIndex = 0;
        int leftIndex = low;
        int leftIndexEnd = mid + 1;
        int rightIndex = mid + 1;
        int rightIndexEnd = high + 1;
        // 这里等于是从两个小数组的开头去遍历
        while (leftIndex != leftIndexEnd || rightIndex != rightIndexEnd) {
            if (leftIndex <= mid && rightIndex <= high) {
                if (array[leftIndex] < array[rightIndex]) {
                    tmpArray[tmpArrayIndex++] = array[leftIndex++];
                } else {
                    tmpArray[tmpArrayIndex++] = array[rightIndex++];
                }
            } else if (leftIndex != leftIndexEnd) {
                tmpArray[tmpArrayIndex++] = array[leftIndex++];
            } else if (rightIndex != rightIndexEnd) {
                tmpArray[tmpArrayIndex++] = array[rightIndex++];
            }
        }


        for (tmpArrayIndex = 0; tmpArrayIndex < tmpArray.length; tmpArrayIndex++) {
            array[low++] = tmpArray[tmpArrayIndex];
        }
    }