归并排序-笔记

算法描述

要将一个数组排序,可以先将数组切分成两半分别排序,然后将有序的两半归并起来。那如何对这两半排序呢?对每一半(递归地)重复“切分成两半,分别排序,归并”的过程,直到每一半大小为1。

算法实现

自顶向下的归并排序

简单的示意图:

Java 实现

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

public void sort(Comparable[] a) {
// 一次性为归并所需的辅助数组分配空间
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}

// 这个 sort 方法的作用其实在于安排多次 merge 方法调用的正确顺序
private void sort(Comparable[] a, Comparable[] aux, int low, int high) {
if (low >= high) {
return;
}

int mid = low + (high-low)/2;
sort(a, aux, low, mid); // 将左半边排序
sort(a, aux, mid+1, high); // 将右半边排序
merge(a, aux, low, mid, high);
}

/**
* 归并两个有序的数组 a[low..mid]、a[mid+1..high]。
* @param a 输入数组
* @param aux 辅助数组
* @param low 要归并的第一个数组的起始索引
* @param mid 要归并的第一个数组的结束索引
* @param high 要归并的第二个数组的结束索引
*/
protected void merge(Comparable[] a, Comparable[] aux, int low, int mid, int high) {
// 前置条件
assert isSorted(a, low, mid);
assert isSorted(a, mid+1, high);

// 复制 a[low..high] 到 aux[low..high]
for (int k = low; k <= high; k++) {
aux[k] = a[k];
}

// i, j 分别是用来遍历两个待归并数组的循环变量
int i = low, j = mid+1;

// 归并回 a[low..high]
for (int k = low; k <= high; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > high) {
a[k] = aux[i++];
} else if (less(aux[i], aux[j])) {
a[k] = aux[i++];
} else {
a[k] = aux[j++];
}
}

// 后置条件
assert isSorted(a, low, high);
}

改进自顶向下的实现

改进思路:

  1. 对小规模子数组使用插入排序。用不同的方法处理小规模问题能改进大多数递归算法的性能,因为递归会使小规模问题中的方法调用过于频繁。
  2. 在要归并的两半都已排序后,如果 a[mid] <= a[mid+1],就跳过 merge() 方法。这个改进使得归并排序对于有序数组的运行时间变为线性的了。
  3. 节省 merge() 方法中将输入数组的部分元素复制到辅助数组所用的时间(但空间无法节省)。这项改进的实现思路:在递归调用的每个层次交换输入数组和辅助数组的角色。

记住一点,不要对算法初始实现的性能盖棺定论!

三项改进的实现:

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

public void sort(Comparable[] a) {
Comparable[] aux = a.clone();
sort(aux, a, 0, a.length - 1);
}

// 这个 sort 方法的作用其实在于安排多次 merge 方法调用的正确顺序
private void sort(Comparable[] src, Comparable[] dst, int low, int high) {
if (high <= low) {
return;
}

// 改进1: 对小规模数组使用插入排序, 防止递归调用过于频繁
if (high-low+1 < 15) {
insertionSort(dst, low, high);
return;
}

int mid = low + (high-low)/2;
sort(dst, src, low, mid); // 将左半边排序
sort(dst, src, mid+1, high); // 将右半边排序

// 改进2: 左右两半都排序后, 如果 a[mid] <= a[mid+1],
// 就无需执行 merge 操作
if (! less(src[mid+1], src[mid])) {
System.arraycopy(src, low, dst, low, high-low+1);
return;
}

merge(src, dst, low, mid, high);
}

@Override
protected void merge(Comparable[] src, Comparable[] dst, int low, int mid, int high) {
// 前置条件
assert isSorted(src, low, mid);
assert isSorted(src, mid+1, high);

int i = low, j = mid+1;
for (int k = low; k <= high; k++) {
if (i > mid) dst[k] = src[j++];
else if (j > high) dst[k] = src[i++];
else if (less(src[i], src[j])) dst[k] = src[i++];
else dst[k] = src[j++];
}

// 后置条件
assert isSorted(dst, low, high);
}

private void insertionSort(Comparable[] a, int start, int end) {
for (int i = start+1; i <= end; i++) {
Comparable item = a[i];
int j = i;
for (; j > start && less(item, a[j-1]); j--) {
a[j] = a[j-1];
}
a[j] = item;
}
}

自底向上的归并排序

自底向上的归并排序比较适合用链表组织的数据,因为只需要重新组织链表链接就能将链表原地排序(不需要创建任何新的链表节点)。

简单的示意图:

Java 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

// sz 要归并的数组的大小
for (int sz = 1; sz < n; sz += sz) {
// 逐对儿归并所有子数组
// 循环条件 i<n-sz 稍做变换就是 mid < n-1, 这样才可以
// 确保 a[mid+1..high] 不为空, 进而确保 merge 操作不会失败
for (int low = 0; low < n - sz; low += 2*sz) {
int mid = low+sz-1;
int high = Math.min(low+2*sz-1, n-1);
merge(a, aux, low, mid, high);
}
}
}

算法性能评估

归并排序最吸引人的性质是它能保证将任何长度为 N 的数组排序所需的运行时间和 $NlogN$ 成正比。主要缺点是所需的额外空间和 N 成正比。

对于长度为 N 的数组,自顶向下的归并排序需要 $(1/2)NlgN$ 至 $NlgN$ 次比较,最多访问数组 $6NlgN$ 次。自底向上也是如此。

参考资源

《算法(第四版)》Robert Sedgewick 等著,第 2 章-排序

0%