经典排序:归并排序

发表于 阅读次数：

介绍

归并排序是一种采用分治思想实现的排序方式，大致的思路如下

把数组从中间分成前后两部分，然后对前后两部分都进行排序（不断分割，分割到一），再把两个排好序的数组合并，就完成啦。

接下来我们详细剖析一下各个步骤，深入理解归并排序。

思路

分解过程

合并过程

实现的细节在代码的注释中，虽然比较多，但希望认真阅读。

下面来看下具体的实现。

实现

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
52
public static void mergeSort(int[] a, int n) {
        mergeSort(a,0,n - 1);
    }
//recursion
private static void mergeSort(int[] a, int left, int right) {
    if(left >= right) return;//无法分解了
    //通过递归分解
    int mid = (left + right) / 2;
    mergeSort(a,left,mid);
    mergeSort(a,mid+1,right);
    //合并
    merge(a,left,mid,right);
}

//将两个数组merge在一起
public static void merge(int[] a, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];//当前需要合并的大小
    //设置两个游标，一个一个元素的对比两个要合并的数组，
    // 小的数进入temp中，当其中一个数组完全进入temp，则另一个数组可以直接全部进去temp，因为这两个数组都是排好序的了
    int i = 0;
    int p1 = left;
    int p2 = mid + 1;
    while(p1 <= mid && p2 <= right) {
        if(a[p1] <= a[p2]) {    //a[p1]小，那就先进去，小细节：这里是<=
            temp[i] = a[p1];    //也就是说在两个元素相同的情况下，把在左边的元素先注入到temp中，从而保证了稳定性
            p1++;
        }else {
            temp[i] = a[p2];    //a[p2]小，那就先进去
            p2++;
        }
        i++;
    }
    //有其中一方结束了
    while(p2 <= right) {    //左边全部进入temp了,就放右边全部人进去
        temp[i++] = a[p2++];    //这里代码就直接这样了，干净点，上面是为了方面阅读
    }
    while(p1 <= mid) {
        temp [i++] = a[p1++];
    }
    //把temp数据复制到a当中即可
    for(i = 0; i < temp.length; i++) {  //把所有temp都装到a中
        a[left + i] = temp[i];  //注意这里必须是a[left + 1]因为你是每次都要merge，不是都从0开始的
    }
}

public static void main(String[] args) {
    int [] a = {4,5,6,3,2,1};
    mergeSort(a,a.length);
    for(int i = 0; i < a.length; i++) {
        System.out.print(a[i]);
    }
}

总结

归并排序是一个稳定的排序算法，其时间复杂度为O(nlogn)，空间复杂度：O(n),因为临时的数组大小不会超过n。

时间复杂度简略分析如下，有兴趣的兄弟萌可以看一下。

设求解a的时间为T(a)，求解b和c的时间为T(b)、T(c)

则T(a) = T(b) + T(c) + K 其中K是合并需要的时间

设对n个元素进行归并排序的时间是T(n)，分解的两个子数组的排序时间是T(n/2),加上合并的n即可

所以公式为 T(n) = 2 * T(n/2) + n;

一步一步分解可以得到 T(n) = 2^kT(n/2^k) + kn， 当T(n/2^k) = T(1)
时，也就是n/2^k = 1,可以得出k = logn

带入上面的公式可得 T(n) = Cn + nlogn，所以时间复杂度是O(nlogn)