归并排序

Wafer Li ... 2017-02-05 《Algorithm 第四版》笔记
  • Algorithm
  • 读书笔记
大约 6 分钟

# 1. 介绍

归并排序是一种递归算法;

其主要思想是分而治之策略,通过将一个大数组分成一个个小数组,通过递归地分割,最后归并成一个有序的数组。

需要注意的是,比较是在归并的过程中实行的,真正实施比较和排序的方法是归并方法,所以才被称为归并排序。

# 2. 归并过程

  1. 复制原数组内容到一个新的辅助数组中

  2. 将辅助数组分为两半

  3. 分别遍历两半部分,将其元素进行比较,按顺序复制回原数组中

# 2.1 实现

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // i 表示左半边,j 表示右半边
    int i = lo, j = mid + 1;

    // Copy the a[lo...hi] to the assistant array
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    for (int k = lo; k <= hi; k++) {

        if (i > mid) {          // 左边空了
            a[k] = aux[j++];
        }
        else if (j > hi) {      // 右边空了
            a[k] = aux[i++];
        }
        else if (less(auk[j], auk[i])) {
            // j 比 i 小,将 j 归并到数组中
            a[k] = aux[j++];
        }
        else {
            // i 比 j 小,将 i 归并到数组中
            a[k] = aux[i++];
        }

    }

}
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

# 3. 自顶向下的归并排序

分治法思想,先排序左半边,后排序右半边,然后将两半归并。

# 3.1 实现

public class Merge {

    private static Comparable[] aux;

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.lenth];
        sort(a, 0, a.lenth - 1);
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;

        sort(a, aux, lo, mid);       // Sort the left side
        sort(a, aux, mid + 1, hi);   // Sort the right side

        merge(a, aux, lo, mid, hi);  // Merge the result
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里 sort() 方法只是对数组进行了简单的分割,而没有进行真正的排序过程

在一些改进版本中,会在数组较小时,采用其他排序方法进行排序。

# 3.2 性能

对于自顶向下的归并排序,需要 12NlogNNlogN{1 \over 2} NlogN \sim NlogN 次比较和 6NlogN6NlogN 次数组访问

# 3.3 改进

# 3.3.1 小数组使用插入排序

由于对于小数组来说,归并会产生不必要的复制消耗;

所以,我们在数组较小时,采用插入排序进行排序过程,而不是全程使用归并算法。

public static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo + CUTOFF - 1) {
        Insertion.sort(a, lo, hi);
        return;
    }

    int mid = lo + (hi - lo) / 2;

    sort(a, lo, mid);       // Sort the left side
    sort(a, mid + 1, hi);   // Sort the right side
    merge(a, lo, mid, hi);  // Merge the result
}
1
2
3
4
5
6
7
8
9
10
11
12

# 3.3.2 避免不必要的归并过程

如果前半边数组和后半边数组 正好构成有序

那就可以直接跳过归并过程,从而节省时间。

public static void sort(Comparable[] a, int lo, int hi) {

    if (hi <= lo + CUTOFF - 1) {
        // 小数组使用插入排序
        Insertion.sort(a, lo, hi);
        return;
    }

    int mid = lo + (hi - lo) / 2;

    sort(a, lo, mid);       // Sort the left side
    sort(a, mid + 1, hi);   // Sort the right side

    if (less(a[mid], a[mid + 1])) {
        // 如果已经有序,则跳过归并过程
        return;
    }

    merge(a, lo, mid, hi);  // Merge the result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 3.3.3 转换数组角色节省拷贝时间

由于归并需要先将原数组的内容拷贝到辅助数组中;

为什么不直接将原输入数组当成辅助数组呢?

所以,我们可以通过将数组的角色调换,以节省拷贝的时间。

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // i 表示左半边,j 表示右半边
    int i = lo, j = mid + 1;

    // 原来的拷贝数组的代码不见了

    // 现在,aux 和 a 角色互换
    for (int k = lo; k <= hi; k++) {

        if (i > mid) {          // 左边空了
            aux[k] = a[j++];
        }
        else if (j > hi) {      // 右边空了
            aux[k] = a[i++];
        }
        else if (less(auk[j], auk[i])) {
            // j 比 i 小,将 j 归并到数组中
            aux[k] = a[j++];
        }
        else {
            // i 比 j 小,将 i 归并到数组中
            aux[k] = a[i++];
        }

    }

}


private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
            if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;

        // 注意,下面 aux 和 a 的顺序互换了
        sort(aux, a, lo, mid);       // Sort the left side
        sort(aux, a, mid + 1, hi);   // Sort the right side

        merge(a, aux, lo, mid, hi);  // Merge the result
    }
}


public static void sort(Comparable[] a) {
    aux = new Comparable[a.length];

    for (int i = 0; i < a.length ; i++) {
        aux[i] = a[i];
    }

    sort(a, aux, 0, a.length - 1);
}
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

# 4. 自底向上的归并排序

它的主要思想是通过不断归并小数组,从而得到一个有序的大数组。 注意与其不同的是,自顶向下是将整个数组分为左右半边分别处理, 而这里的方法是将整个数组都打散为小数组之后再行合并。

# 4.1 实现

public class  MergeBU {
    private static Comparable[] aux;

    public static void sort(Comparable[] a) {
        int N = a.lenth;
        aux = new Comparable[N];

        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N - sz; lo + = sz + sz) {
                merge (a, log, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意这里使用了循环的版本,而不是递归的版本

# 4.2 性能

对于一个长度为 N 的数组,自底向上的归并排序需要 12NlogNNlogN{1 \over 2} NlogN \sim NlogN 次比较和最多 6NlogN6NlogN 次的数组访问

# 5. 比较

  1. 当数组长度为 2 的幂的时候,这两个方法需要的开支是相同的

    它们的时间复杂度的增长级别是相同的,数组访问的增长级别也是相同的

  2. 自底向上的归并排序适合于使用链表作为数据结构的数据,由于它只需要调整数组链接即可,而不需要去创建新的链表节点

  3. 由于自底向上使用的是循环算法,一般来说都要比使用递归算法的自顶向下的归并排序要快

# 6. 展望

归并排序是基于比较的排序算法渐进最优

归并排序确保了 即使在最坏情况,所需要的最少比较次数都是 NlogN\sim NlogN

由于没有一个基于比较的排序算法能保证所需要的最少次数都比 log(N!)log(N!) 要少,由于 log(N!)NlogNlog(N!) \sim NlogN,所以归并排序是渐进最优基于比较的排序算法

基于比较的排序可以由决策树来描述。

树的高度 hh 即为所需要进行的比较次数,由排列原理可知,NN 个元素有 N!N! 中排序方式,一个决策树的叶子个数必须要能容纳下 N!N! 中排序结果,否则将无法完成排序

因为如果不能容纳下所有的结果,一旦输入改变,那么得出的排序结果就可能是错误的。

所以一棵比较算法的决策树,至少N!N! 个叶节点,而高为 hh 的树具有最多叶节点个数为 2h2^h,则有:

2hleavesN!hlg(N!)NlogN\begin{aligned} 2^h \ge leaves \ge N! \\ \Rightarrow \ h \ \ge \ lg(N!) \sim NlogN \end{aligned}