归并排序

1. 介绍

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

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

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

2. 归并过程

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

  2. 将辅助数组分为两半

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

2.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
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++];
}

}

}

3. 自顶向下的归并排序

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

3.1 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
}
}

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

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

3.2 性能

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

3.3 改进

3.3.1 小数组使用插入排序

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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
}

3.3.2 避免不必要的归并过程

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
}

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

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

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

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

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
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);
}

4. 自底向上的归并排序

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

4.1 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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));
}
}
}
}

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

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! h  lg(N!)NlogN\begin{aligned} 2^h \ge leaves \ge N! \\ \Rightarrow \ h \ \ge \ lg(N!) \sim NlogN \end{aligned}