Hello World

吞风吻雨葬落日 欺山赶海踏雪径

0%

归并排序

发表于 更新于 分类于

归并排序

说明

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案处理合并，即分而治之)。

归并排序

可以看到这种结构很像一棵完全二叉树，通常归并排序采用递归方法实现，递归深度为log2n。

代码实现

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class MergeSort implements Sorter {
    @Override
    public int[] sort(int[] a) {

        if (a.length <= 1) {
            return a;
        }

        //定义新空间临时存放局部有序的数据
        int[] t = new int[a.length];
        //
        sort(a, 0, a.length - 1, t);

        return a;
    }

    private void sort(int[] a, int start, int end, int[] tmp) {

        if (start < end) {
            //分成两部分
            int mid = (start + end)/ 2;
            //递归分左半部分
            sort(a, start, mid, tmp);
            //递归分右半部分
            sort(a, mid + 1, end, tmp);
            //以上递归结束后开始合并刚才左右两个数据
            merge(a, start, mid, end, tmp);
        }
    }

    private void merge(int[] a, int s, int m, int e, int[] tmp) {
        //左半部分的指针
        int i = s;
        //右半部分的指针
        int j = m + 1;
        //tmp的指针（0就可以，临时的）
        int p = 0;
        //两个不部分比出最小的加入tmp
        while (i <= m && j <= e) {
            if (a[i] < a[j]) {
                tmp[p++] = a[i++];
            } else {
                tmp[p++] = a[j++];
            }
        }

        //补上剩余的
        while (i <= m) {
            tmp[p++] = a[i++];
        }
        while (j <= e) {
            tmp[p++] = a[j++];
        }

        //合并保证a的s->e是有序的（此块有序后才能继续合并）
        System.arraycopy(tmp,0,a,s,(e-s+1));
        //for (i = 0;i<p;i++){
        //    a[s+i] = tmp[i];
        //}

    }

    public static void main(String[] args) {

        int [] arr = new int[]{6,1,2,7,9,8,4,5,0,8,10,12,2,5};
        Sorter s = new MergeSort();
        s.sort(arr);
        s.print(arr);
    }
}

分析

时间复杂度

归并排序的时间复杂度是O(NlogN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(NlogN)。

稳定性

归并排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 – 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

TimSort

java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。

参考

图解排序算法(四)之归并排序
https://www.cnblogs.com/chengxiao/p/6194356.html

Java实现归并排序
https://www.cnblogs.com/of-fanruice/p/7678801.html

timsort
http://svn.python.org/projects/python/trunk/Objects/listsort.txt

还有一篇有意思的：
如何找出Timsort算法和玉兔月球车中的Bug
http://www.freebuf.com/vuls/62129.html