Fork me on GitHub
image frame

Konglong's blog

Knowledge advances by steps and not by leaps.

用优先队列解决TopM和Multiway问题

TopM 问题描述

从 N 个输入中找到最大/小的 M 个元素。

使用基于堆的优先队列解决 TopM 问题

算法描述

解决此问题的算法不止一个,但这里只关注下面这个:
将前 M 个输入读入一个大小为 M 的集合 S,并使集合 S 中的最小元素位于位置 k。为了方便描述,将集合 S 中的最小元素记为 $E_k$。当再读入一个新的输入时,将其与 $E_k$ 进行比较,若新的输入较大,就从集合 S 中删除当前的 $E_k$,并将新的输入添加至集合 S,然后找出新的 $E_k$。处理完所有输入后,就得到最大的 M 个输入。

算法实现

创建一个大小为 M+1 的 MinPQ,将 N 个输入插入此优先队列,每次插入完成后就检查队列大小是否大于 M,如果大于就删除最小元素。

下面的示例代码找出交易金额最大的 M 笔交易:

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

public static void main(String[] args) {
int M = Integer.valueOf(args[0]);
MinPQ<Transaction> pq = new MinPQ<Transaction>(M+1);
while (StdIn.hasNextLine()) {
pq.insert(new Transaction(StdIn.readLine()));
if (pq.size() > M) {
pq.delMin();
}
} // 最大的 M 个元素都在优先队列中

Stack<Transaction> stack = new Stack<Transaction>();
while (!pq.isEmpty()) {
stack.push(pq.delMin());
}
for (Transaction t : stack) {
StdOut.println(t);
}
}

性能评估

从 N 个输入中找到最大的 M 个元素所需的时间成本:

解决办法 时间的增长数量级 空间的增长数量级
使用排序算法 $NlogN$ N
使用初级实现的优先队列 NM M
使用基于堆的优先队列 $NlogM$ M

Multiway 问题描述

将多个有序的输入流归并成一个有序的输入流。也就是常说的多路/向归并问题。

使用基于堆的索引优先队列解决多路归并问题

算法描述

算法思路如图所示,其中的前提是每个流都是单独升序有序的:

将多个升序有序的流归并

使用索引优先队列实现算法

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

public class Multiway {

// Merge together the sorted input streams
// and write the sorted result to standard output
public static void merge(In[] streams) {
int n = streams.length;
IndexedMinPQ<String> pq = new IndexedMinPQ<String>(n);

for (int i = 0; i < n; i++) {
if (!streams[i].isEmpty()) {
pq.insert(i, streams[i].readString());
}
}

while (!pq.isEmpty()) {
StdOut.print(pq.min() + " ");
int i = pq.delMin();
if (!streams[i].isEmpty()) {
pq.insert(i, streams[i].readString());
}
}
}

public static void main(String[] args) {
int n = args.length;
In[] streams = new In[n];
for (int i = 0; i < n; i++) {
streams[i] = new In(args[i]);
}
merge(streams);
}
}

索引优先队列

API

定义 描述
void insert(int i, Item item) 插入一个元素,将它和索引 i 关联
void change(int i, Item item) 将与索引 i 关联的元素设置为 item
bool contains(int i) 是否存在索引为 i 的元素
void delete(int i) 删除索引 i 及其关联的元素
void min() 返回最小元素
int minIndex() 返回最小元素的索引
int delMin() 删除最小元素并返回它的索引
bool isEmpty() 优先队列是否为空
int size() 优先队列中的元素数量

基于堆的实现

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309

public class IndexedMinPQ<E extends Comparable<E>> implements Iterable<Integer> {

private int maxN; // 优先队列可容纳的最大元素个数
private int n; // 当前优先队列上的元素个数

// 保存用户输入的元素,下标就是对应元素的索引
private E[] items;

// 二叉堆的数组表示形式。节点之间的父子关系仍使用下标表示,
// 但下标对应的元素不是输入元素,而是输入元素的索引
private int[] pq;

// 保存输入元素的索引在二叉堆中的位置,下标就是输入元素的索引
private int[] qp;

public IndexedMinPQ(int maxN) {
if (maxN < 0) {
throw new IllegalArgumentException("maxN < 0");
}
this.maxN = maxN;
n = 0;
items = (E[]) new Comparable[maxN+1];
pq = new int[maxN+1];
qp = new int[maxN+1];
for (int i = 0; i <= maxN; i++) {
qp[i] = -1;
}
}

/**
* 插入一个索引为 i 的元素
* @param i
* @param item
*/
public void insert(int i, E item) {
if (i < 0 || i >= maxN) {
throw new IndexOutOfBoundsException("i < 0 or i >= maxN");
}
if (contains(i)) {
throw new IllegalArgumentException("Index i already exists");
}

items[i] = item;
pq[++n] = i;
qp[i] = n;
percolateUp(n);
}

/**
* 将索引为 i 的元素设置为 item
* @param i
* @param item
*/
public void change(int i, E item) {
if (i < 0 || i >= maxN) {
throw new IndexOutOfBoundsException("k < 0 or k >= maxN");
}
if (!contains(i)) {
throw new NoSuchElementException("Index i is absent");
}

E oldItem = items[i];
items[i] = item;
if (item.compareTo(oldItem) > 0) {
percolateDown(qp[i]);
} else {
percolateUp(qp[i]);
}
}

/**
* 是否存在索引为 i 的元素
*/
public boolean contains(int i) {
return qp[i] != -1;
}

/**
* 删除索引为 i 的元素
*/
public void delete(int i) {
if (i < 0 || i >= maxN) {
throw new IndexOutOfBoundsException("k < 0 or k >= maxN");
}
if (!contains(i)) {
throw new NoSuchElementException("Index i does not exist");
}

int heapIndex = qp[i];
exch(heapIndex, n--);
percolateUp(heapIndex);
percolateDown(heapIndex);
items[i] = null;
pq[n+1] = -1; // 重置为初始值,可选
qp[i] = -1;
}

/**
* 返回最小元素
*/
public E min() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return items[pq[1]];
}

/**
* 返回最小元素的索引
*/
public int minIndex() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}

/**
* 删除最小元素并返回它的索引
*/
public int delMin() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
int indexOfMin = pq[1];
exch(1, n--);
percolateDown(1);
assert indexOfMin == pq[n+1];
items[indexOfMin] = null;
pq[n+1] = -1; // 重置为初始值,可选
qp[indexOfMin] = -1;
return indexOfMin;
}

/**
* 减小与索引 i 关联的元素的键值(key value)
* @param i 键值要减小的元素的索引
* @param item 键值减小后的元素
*/
public void decreaseKey(int i, E item) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index i is absent");
if (items[i].compareTo(item) <= 0)
throw new IllegalArgumentException(
"Calling decreaseKey() with given argument would not strictly decrease the key");
items[i] = item;
percolateUp(qp[i]);
}

/**
* 增大与索引 i 关联的元素的键值(key value)
* @param i 键值要增大的元素的索引
* @param item 键值增大后的元素
*/
public void increaseKey(int i, E item) {
if (i < 0 || i >= maxN) throw new IndexOutOfBoundsException();
if (!contains(i)) throw new NoSuchElementException("index i is absent");
if (items[i].compareTo(item) >= 0)
throw new IllegalArgumentException(
"Calling increaseKey() with given argument would not strictly increase the key");
items[i] = item;
percolateDown(qp[i]);
}

public boolean isEmpty() {
return n == 0;
}

public int size() {
return n;
}

/*******************************
* General helper functions.
*******************************/

/**
* i 索引的元素是否大于 j 索引的
* @param i 第一个元素的索引在二叉堆中的位置
* @param j 第二个元素的索引在二叉堆中的位置
* @return
*/
private boolean greater(int i, int j) {
return items[pq[i]].compareTo(items[pq[j]]) > 0;
}

/**
* 第一个索引对应的元素是否大于第二个
* @param i1 第一个元素的索引
* @param i2 第二个元素的索引
* @return
*/
private boolean greater2(int i1, int i2) {
return items[i1].compareTo(items[i2]) > 0;
}

private void exch(int i, int j) {
int tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
qp[pq[i]] = i;
qp[pq[j]] = j;
}

/****************************
* Heap helper functions.
****************************/
private void percolateUp(int i) {
int tmp = pq[i];
int hole = i;
while (hole > 1 && greater2(pq[hole/2], tmp)) {
pq[hole] = pq[hole/2];
qp[pq[hole]] = hole;
hole = hole/2;
}
pq[hole] = tmp;
qp[tmp] = hole;
}

private void percolateDown(int i) {
int tmp = pq[i];
int hole = i;
while (2*hole <= n) {
int child = 2*hole;
// 找出较小的儿子
if (child+1 <= n && greater(child, child+1)) {
child++;
}
if (greater2(tmp, pq[child])) {
pq[hole] = pq[child];
qp[pq[hole]] = hole;
hole = child;
} else {
break;
}
}
pq[hole] = tmp;
qp[tmp] = hole;
}

/****************************
* Iterators.
****************************/

public Iterator<Integer> iterator() {
return new HeapIterator();
}

private class HeapIterator implements Iterator<Integer> {

private IndexedMinPQ<E> copy;

public HeapIterator() {
// pq.length-1 = maxN
copy = new IndexedMinPQ<E>(pq.length-1);
// Adding all elements to copy of heap
// takes linear time since already in heap order so no elements move
for (int i = 1; i <= n; i++) {
copy.insert(pq[i], items[pq[i]]);
}

// Bad performance: NlogN. Should not use!
/*for (int i = 0; i < n; i++) {
copy.insert(i, items[i]);
}*/
}

public boolean hasNext() {
return !copy.isEmpty();
}

public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}

public void remove() {
throw new UnsupportedOperationException();
}
}

/**
* Unit tests the <tt>IndexedMinPQ</tt> data type.
*/
public static void main(String[] args) {
// insert a bunch of strings
String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };

IndexedMinPQ<String> pq = new IndexedMinPQ<String>(strings.length);
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}

// delete and print each key
while (!pq.isEmpty()) {
int i = pq.delMin();
StdOut.println(i + " " + strings[i]);
}
StdOut.println();

// reinsert the same strings
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}

// print each key using the iterator
for (int i : pq) {
StdOut.println(i + " " + strings[i]);
}
while (!pq.isEmpty()) {
pq.delMin();
}
}
}

性能评估

在一个大小为 N 的索引优先队列中,插入(insert)、改变优先级(change)、删除(delete)和删除最小元素(delMin)操作所需的比较次数和 $logN$ 成正比。

含有 N 个元素的基于堆的索引优先队列所有操作在最坏情况下的时间成本:

操作 比较次数的增长数量级
insert() $logN$
change() $logN$
contains() 1
delete() $logN$
min() 1
minIndex() 1
delMin() $logN$

参考资源

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

堆排序-笔记

算法概述

有了前一篇 优先队列与堆 的铺垫,理解堆排序就容易多了。基本思想就是由所有待排序元素构建一个可删除最大元素的堆,然后重复删除最大元素即可将它们按顺序删去。如果用无序数组实现的优先队列,这么做相当于进行一次插入排序。用基于堆的优先队列,就产生一种新的排序算法-堆排序。

算法描述与实现

显然,堆排序可以分为两个阶段:在堆的构造阶段,将原始数组重新安排组织进一个堆中;然后在下沉排序阶段,从堆中按递减顺序取出所有元素就得到最终的排序结果。

堆的构造在前一篇中已经详细讲述过,这里不再重复。不过之前的构造实现是将需要排序的数组拷贝一份,将副本用作堆,而这里的实现将需要排序的数组本身作为堆,这样就无需任何额外空间。下沉排序的工作就是将堆中最大元素(根元素)和堆尾元素交换位置,然后堆大小减一,接着下沉新的根元素以恢复堆序性(换个方式描述就是删除最大元素,然后放入堆缩小后堆尾之后空出的位置),重复此过程,直到堆缩小为一。整个排序过程和选择排序有些类似,不断选择出剩余之中最大的,但所需的比较要少得多。

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) {
int n = a.length;

// 构造阶段
for (int k = n/2; k >= 1; k--) {
sink(a, k, n);
}

// 下沉排序阶段
while (n > 1) {
exch(a, 1, n--);
sink(a, 1, n);
}
}

private void sink(Comparable[] a, int k, int n) {
Comparable tmp = get(a, k);
int hole = k;
while (2*hole <= n) {
int child = 2*hole;
// 找到较大的儿子
if ((child+1) <= n && less(a, child, child+1)) {
child++;
}
if (less(tmp, get(a, child))) {
move(a, child, hole);
hole = child;
} else {
break;
}
}
set(a, hole, tmp);
}

protected boolean less(Comparable[] a, int i, int j) {
return less(a[i-1], a[j-1]);
}

protected void exch(Object[] a, int i, int j) {
Object t = a[i-1];
a[i-1] = a[j-1];
a[j-1] = t;
}

private Comparable get(Comparable[] a, int i) {
return a[i-1];
}

private void set(Comparable[] a, int i, Comparable v) {
a[i-1] = v;
}

private void move(Object[] a, int from, int to) {
a[to-1] = a[from-1];
}

算法性能评估

用 sink 操作由 N 个元素构造堆只需少于 2N 次比较以及少于 N 次交换。

将 N 个元素排序,堆排序只需少于 $(2NlgN+2N)$ 次比较,以及一半次数的交换。其中 2N 项来自于堆的构造。

堆排序是我们所知的唯一能够同时最优地利用时间和空间的方法——在最坏情况下它也能保证使用 ~$2NlgN$ 次比较和恒定的额外空间。因此在空间十分紧张的时候,它也有较好的性能,例如在嵌入式系统和低成本的移动设备中。但现代系统中的许多应用并不使用它,因为它无法利用缓存。数组元素很少和相邻的元素进行比较,导致缓存未命中的次数远远高于大多数比较都在相邻元素间进行的算法,如快速排序、归并排序,甚至是希尔排序。

另一个优点是它能在插入操作和删除最大/小元素操作混合的动态场景中保证对数级别的运行时间。

参考资源

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

优先队列与堆-笔记

引言

许多应用程序都需要处理有序的元素,但不一定要求他们全部有序,或者不一定要一次就将它们排序。很多情况下我们会先收集一些元素,处理当前键值最大的元素,然后再收集一些元素,再处理当前键值最大的元素,如此这般。例如,操作系统的进程调度、打印机中的打印任务调度等。

对于这些应用场景,一个合适的数据结构应该支持两种操作:删除最大/小元素、插入元素。这种数据结构叫做优先队列。

优先队列还可以作为算法设计工具用来构造其他算法,例如用来实现堆排序算法、以它为基础开发数据压缩算法、抽象若干重要的图搜索算法等等。

API

优先队列最重要的操作就是删除最大/小元素和插入元素。

MaxPQ(max priority queue) 的 API:

  • 构造器,此处省略了
  • void insert(Key v) 插入一个元素
  • Key max() 返回最大元素
  • Key delMax() 删除并返回最大元素
  • boolean isEmpty() 返回队列是否为空
  • int size() 返回优先队列中的元素个数

MinPQ 的 API 和 MaxPQ 类似,用 delMin() 替换 delMax() 就行了,也很容易实现。

初级实现

无序数组实现。要实现删除最大元素操作,先找到最大元素,将它和边界元素交换位置,然后删除边界元素。

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

protected Key[] items;
protected int n;

public void insert(Key v) {
if (n == items.length) {
resize(2 * items.length);
}
items[n++] = v;
}

public Key max() {
if (isEmpty()) {
throw new NoSuchElementException("ArrayMaxPQ underflow");
}
int posOfMax = posOfMax();
return items[posOfMax];
}

public Key delMax() {
if (isEmpty()) {
throw new NoSuchElementException("ArrayMaxPQ underflow");
}

int posOfMax = posOfMax();
exch(items, posOfMax, n-1);
Key max = items[--n];
items[n] = null;
if (n > 0 && n == items.length/4) {
resize(items.length/2);
}
return max;
}

private int posOfMax() {
int posOfMax = 0;
for (int i = 1; i < n; i++) {
if (less((Comparable) items[posOfMax], (Comparable) items[i])) {
posOfMax = i;
}
}
return posOfMax;
}

protected void resize(int capacity) {
assert capacity > n;
Key[] temp = (Key[]) new Object[capacity];
for (int i = 0; i < n; i++) {
temp[i] = items[i];
}
items = temp;
}

有序数组实现。插入元素时,将较大元素向右移动一格以使数组保持有序(和插入排序一样)。

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

public void insert(Key v) {
if (n == items.length) {
resize(2 * items.length);
}

int i = n;
for (; i > 0 && less((Comparable) v, (Comparable) items[i-1]); i--) {
items[i] = items[i-1];
}
items[i] = v;
n++;
}

public Key max() {
if (isEmpty()) {
throw new NoSuchElementException("ArrayMaxPQOrderly underflow");
}
return items[n-1];
}

public Key delMax() {
if (isEmpty()) {
throw new NoSuchElementException("ArrayMaxPQOrderly underflow");
}
Key max = items[--n];
items[n] = null;
if (n > 0 && n == items.length/4) {
resize(items.length/2);
}
return max;
}

链表表示法也有两种:惰性方法,使用无序序列,删除时才找出最大元素;积极方法,使用有序序列,插入时就保持列表有序。下面是积极方法的实现:

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

private Node<Key> first;
private int n;

private static class Node<Key> {
Key item;
Node next;
}

public LinkListMaxPQ() {
n = 0;
}

/**
* 插入新元素, 并保持倒序排列
* @param v
*/
public void insert(Key v) {
Node<Key> newNode = new Node<Key>();
newNode.item = v;

Node<Key> prev = null;
Node<Key> curr = first;
while (curr != null && less((Comparable) v, (Comparable) curr.item)) {
prev = curr;
curr = curr.next;
}
if (prev == null) { // 队列为空或者新元素要排在 first 之前
newNode.next = first;
first = newNode;
} else {
newNode.next = prev.next;
prev.next = newNode;
}
n++;
}

public Key max() {
if (isEmpty()) {
throw new NoSuchElementException("ArrayMaxPQ underflow");
}
return first.item;
}

public Key delMax() {
if (isEmpty()) {
throw new NoSuchElementException("ArrayMaxPQ underflow");
}
Key max = first.item;
first = first.next;
n--;
return max;
}

基于堆的实现

什么是堆

首先,当堆(heap)这个词不加修饰地用在优先队列的上下文中时,一般都是指二叉堆这种数据结构。而二叉堆其实就是一棵二叉树,但它还有两个性质,结构性和堆序性(heap-order property),这点和二叉查找树一样。简单起见,下文就把二叉堆叫做堆。

结构性

一棵二叉树,其元素总是从左到右层层填入(要么树被完全填满,要么就只有最底层未填满),这样的树被称为完全二叉树(complete binary tree)。堆就是一棵完全二叉树。一棵完全被填满的二叉树也被称为理想二叉树。

堆序性

当一棵二叉树的每个节点都大于等于它的两个子节点时,它被称为是堆有序的。 堆也是一棵堆有序的二叉树。

因此,二叉堆就是一棵堆有序的完全二叉树。 堆的操作可能会破坏两个性质中的一个,因此,堆的操作必须到其所有性质都被满足时才能终止。

如何表示堆

对于完全二叉树,可以将数组下标用作节点指针,这样就可以将其节点按照层次顺序放入数组中,根节点在位置 1,它的子节点在位置 2 和 3,而子节点的子节点则分别在位置 4、5、6 和 7,以此类推。位置规律:位置 k 的节点的父节点的位置为 $\lfloor k/2 \rfloor$,而它的两个子节点的位置分别为 2k 和 2k+1。注意,不使用数组的第一个位置,因为当 k=0 时,这条规律就跟实际情况冲突了!

注意,对于非完全二叉树,上述位置规律并不适用。我们倒是可以使用这个规律来验证一棵二叉树是否是完全二叉树。

将完全二叉树展现为树形结构时,就很容易理解下面两条结论:

  1. 一棵高为 h 的完全二叉树有 $2^h$ 到 $2^{h+1} - 1$ 个节点。注意,根节点的 h 为 0。
  2. 一棵大小为 N 的完全二叉树的高度为 $\lfloor lgN \rfloor$。

堆的操作

堆的操作会先打破堆的有序状态,然后再遍历堆并将其状态恢复,这个过程叫做堆的有序化(reheapifying)。

堆的有序化有两种情况:节点的键值增大或者在堆底插入一个新元素时,需要由下至上恢复堆的顺序;节点的键值减小或者根节点被替换为一个较小的元素时,需要由上至下恢复堆的顺序。由下至上的堆有序化叫做上浮(swim)或向上渗透(percolate up),由上至下的堆有序化叫做下沉(sink)或向下渗透(percolate up)。

我们先看如何实现上浮、下沉这两个辅助操作,再看如何用这两个辅助操作实现插入、删除操作。

上浮操作(swim)

当某个节点比它的父节点更大时,该节点不断上浮,直到整个堆再次有序。有两种实现:

  1. 跟父节点比较,如果父节点小,就交换位置。重复该过程,直到遇到一个不小于它的父节点或到达堆的顶部
  2. 在下一个可用位置创建一个空位(针对插入新元素)或将键值变化的节点另存并将其所在位置置为空,然后检查 X 元素(即新元素或键值变化的元素)放在空位会不会破坏堆的序。如果不会,就将 X 元素放进空位,操作完成。否则,就将父节点的元素移入空位,这样空位就上浮至父节点所在位置,重复此过程,直到 X 能被放入空位为止。

第二种实现似曾相识,插入排序的一种优化方式就是将大于 X 的所有元素向后移动一格,然后直接插入。与不断交换的实现方式(第一种实现)相比,这种更高效,因为赋值操作更少了。

下沉操作(sink)

当某个节点比它的两个子节点或其中之一更小时,该节点不断下沉,直到整个堆再次有序。同样地,该操作也有两种实现,实现思想与上浮操作基本相同,这里不再啰嗦。注意边界条件测试,以及与较大的子节点进行比较即可。

插入元素

添加元素时,要从树顶向下一层一层从左向右填入新元素,这样才能确保添加新元素后它仍然是一棵完全二叉树,即保持了二叉树的结构性。对于数组表示形式来说,等价的描述就是将新元素添加到数组末尾,增加堆的大小并让新元素上浮到合适的位置。

删除最大/小元素

从数组顶端删除最大/小元素,并将数组的最后一个元素放到顶端,减小堆的大小并让这个元素下沉到合适的位置。

构建堆(buildHeap)

两种实现:

  1. 逐个将输入元素插入到空优先队列。这种实现的运行时间与 $NlogN$ 成正比。
  2. 从右向左对前 1/2 的元素进行 sink 操作。之所以只扫描前 1/2,是因为对于二叉堆来说,至少有一半的节点是叶节点,具体证明请看 证明二叉堆至少有一半的节点是叶节点用 sink 操作由 N 个元素构造堆只需少于 2N 次比较以及少于 N 次交换。

基于堆的优先队列

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220

public class MaxPQ<Key> implements Iterable<Key> {

private Key[] pq; // store items at indices 1 to n
private int n; // number of items on priority queue
private Comparator<Key> comparator; // optional comparator

public MaxPQ() {
this(1);
}

public MaxPQ(int initCapacity) {
this(initCapacity, null);
}

public MaxPQ(Comparator<Key> comparator) {
this(1, comparator);
}

public MaxPQ(int initCapacity, Comparator comparator) {
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
this.comparator = comparator;
}

public MaxPQ(Key[] keys) {
n = keys.length;
pq = (Key[]) new Object[keys.length + 1];
for (int i = 0; i < n; i++) {
pq[i + 1] = keys[i];
}
for (int k = n / 2; k >= 1; k--) {
sink(k);
}
assert isMaxHeap();
}

// 跟父节点比较,如果父节点小,就交换位置。
// 重复该过程,直到遇到一个不小于它的父节点或到达堆的顶部
public void insert(Key x) {
// double size of array if necessary
if (n >= pq.length - 1) {
resize(2 * pq.length);
}

// add x, and percolate it up to maintain heap invariant
pq[++n] = x;
swim(n);
assert isMaxHeap();
}

// 在下一个可用位置创建一个空位, 然后检查 X 元素(即新元素)放在空位会不会破坏堆的序。
// 如果不会,就将 X 元素放进空位,操作完成。否则,就将父节点的元素移入空位,
// 这样空位就上浮至父节点所在位置,重复此过程,直到 X 能被放入空位为止。
public void insert2(Key x) {
// double size of array if necessary
if (n >= pq.length - 1) {
resize(2 * pq.length);
}

pq[++n] = x;
int hole = n;
percolateUp(hole);
assert isMaxHeap();
}

public Key delMax() {
if (isEmpty()) {
throw new NoSuchElementException("Priority queue underflow");
}
Key max = pq[1];
pq[1] = pq[n--];
pq[n + 1] = null; // to avoid loitering and help with garbage collection
sink(1);
if (n > 0 && (n == (pq.length - 1) / 4)) {
resize(pq.length / 2);
}
assert isMaxHeap();
return max;
}

public Key delMax2() {
if (isEmpty()) {
throw new NoSuchElementException("Priority queue underflow");
}
Key max = pq[1];
pq[1] = pq[n--];
pq[n+1] = null; // 防止对象游离
percolateDown(1);
if (n > 0 && (n == (pq.length - 1) / 4)) {
resize(pq.length / 2);
}
assert isMaxHeap();
return max;
}

public Key max() {
if (isEmpty()) {
throw new NoSuchElementException("Priority queue underflow");
}
return pq[1];
}

public boolean isEmpty() {
return n == 0;
}

public int size() {
return n;
}

// helper function to double the size of the heap array
private void resize(int capacity) {
assert capacity > n;
Key[] temp = (Key[]) new Object[capacity];
for (int i = 1; i <= n; i++) {
temp[i] = pq[i];
}
pq = temp;
}

/*****************************************************
* Helper functions to restore the heap invariant.
*****************************************************/

// 不断地交换元素位置
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}

// 不断地交换元素位置
private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
// j < n 等价于 j+1 <= n
if (j < n && less(j, j+1)) { // 找出较大的, 而非较小的
j++;
}
if (!less(k, j)) {
break;
}
exch(k, j);
k = j;
}
}

// 不断地向下移动元素使空位向上渗透
private void percolateUp(int hole) {
Key x = pq[hole];
while (hole > 1 && less(pq[hole/2], x)) {
pq[hole] = pq[hole/2];
hole = hole/2;
}
pq[hole] = x;
}

// 不断地向上移动元素使空位向下渗透
private void percolateDown(int hole) {
Key tmp = pq[hole];
while (2*hole <= n) {
int j = 2*hole;
if ((j+1) <= n && less(j, j+1)) { // 找出较大的, 而非较小的
j = j+1;
}

if (less(tmp, pq[j])) {
pq[hole] = pq[j];
hole = j;
} else {
break;
}
}
pq[hole] = tmp;
}

/**********************************************
* Helper functions for compares and swaps.
**********************************************/

private boolean less(int i, int j) {
if (comparator == null) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
} else {
return comparator.compare(pq[i], pq[j]) < 0;
}
}

private boolean less(Key key1, Key key2) {
if (comparator == null) {
return ((Comparable<Key>) key1).compareTo(key2) < 0;
} else {
return comparator.compare(key1, key1) < 0;
}
}

private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}

// is pq[1..N] a max heap?
private boolean isMaxHeap() {
return isMaxHeap(1);
}

// is subtree of pq[1..n] rooted at k a max heap?
private boolean isMaxHeap(int k) {
if (k > n) return true;
int left = 2 * k;
int right = 2 * k + 1;
if (left <= n && less(k, left)) return false;
if (right <= n && less(k, right)) return false;
return isMaxHeap(left) && isMaxHeap(right);
}

}

算法性能评估

对于一个含有 N 个元素的基于堆的优先队列,插入元素操作只需不超过 $(lgN+1)$ 次比较,删除最大元素操作需要不超过 $2lgN$ 次比较。

优先队列的各种实现在最坏情况下运行时间的增长数量级

数据结构 插入元素 删除最大元素
有序数组 N 1
无序数组 1 N
$logN$ $logN$
理想情况 1 1

参考资源

《算法(第四版)》Robert Sedgewick 等著,第 2 章-排序
《数据结构与算法分析-Java语言描述》Mark Allen Weiss 著,第 6 章-优先队列(堆)

快速排序-笔记

算法描述

Hoare 在 1960 年发明了这个算法,该算法的思路是选择一个元素作为切分元素,并排定它在数组中的位置,使得它左边的元素都小于等于它,右边的都大于等于它;然后分别递归地对左右两部分重复前面的过程。如果每个元素左边的小于等于它,右边的元素大于等于它,整个数组就有序了。

算法实现

先看基于二向切分的基本实现。切分数组的过程如下图:

二向切分的示意图

具体实现:

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

public void sort(Comparable[] a) {
StdRandom.shuffle(a); // 消除对输入的依赖
sort(a, 0, a.length-1);
}

private void sort(Comparable[] a, int low, int high) {
if (high <= low) return;
int k = partition(a, low, high); // 切分
sort(a, low, k-1); // 将左半部分a[low..k-1]排序
sort(a, k+1, high); // 将右半部分a[k+1..high]排序
}

/**
* 为子数组选定切分元素, 并排定它在数组中的位置。
* 排定位置后, 它左边的所有元素都小于等于它, 右边的都大于等于它。
* @param a 输入数组
* @param low 子数组起始位置
* @param high 子数组结束位置
* @return 排定位置之后切分元素的索引
*/
private int partition(Comparable[] a, int low, int high) {
Comparable v = a[low]; // 选定切分元素
int i = low, j = high + 1; // 左右扫描指针

while (true) {
// 等价的写法, 但可读性没有下面的写法好
//while (less(a[++i], v) && i < high) {}
//while (less(v, a[--j]) && j > low) {}

while (less(a[++i], v)) if (i == high) break;
while (less(v, a[--j])) if (j == low) break;
if (i >= j) {
break;
}
// 能走到这里表明 i < j。在 i < j 这个前提下, 前面两个循环
// 退出的原因只能是找到了我们希望的元素, 因此执行交换操作
exch(a, i, j);
}
exch(a, low, j); // 将切分元素 v 放入正确的位置
// 此时 a[low..j-1] <= a[j] <= a[j+1..high] 已达成
return j;
}

/**
* 展现很容易犯的错误
*/
private int wrongPartition(Comparable[] a, int low, int high) {
Comparable v = a[low]; // 选定切分元素
int i = low, j = high + 1; // 左右扫描指针

while (true) {
// TODO 错误写法一: 循环很可能在 因数组下标越界而抛出异常 时才退出。
// 之所以会犯这个错是因为正确的代码在循环体中有检查是否达到上下界,
// 达到则直接 break。想把循环体精简掉时就想当然地把上下界包含到了循环条件中了
while (less(a[++i], v) && i <= high) {}
while (less(v, a[--j]) && j >= low) {}

// TODO 错误写法二: 数组下标会越界
// j 初始值为 high+1, i 等于 high+1 时,
// 如果 high 是输入数组最后一个元素的索引, 那么第一次执行该循环时下标就会越界;
// 如果 high 之后还有元素, 那么就会操作到其他子数组的元素了, 导致最终的结果并不是有序的
while (less(a[++i], v) && i <= j) {}
while (less(v, a[--j]) && i <= j) {}

// TODO 错误写法三: 数组下标还是会越界
// 很可能会觉得把错误写法二这样修改哈就正确了, 但实际上仍然会下标越界。
// 因为 j 初始值为 high+1, 第一次执行该循环时, 在将 i 更新为 high 后,
// 还要再检查一次循环条件以退出循环, 这时就会出现跟错误二同样的情形
while (less(a[++i], v) && i < j) {}
while (less(v, a[--j]) && i < j) {}

// TODO 错误写法四: i, j 永远碰不了头, 进而导致外层循环死循环
// 很可能会觉得把错误写法三这样改改就好了, 可问题是之前的错误解决了, 却引入了新的错误。
// 因为循环条件包含 i < j-1, 所以 i == j-1 时两个循环就退出了, 那 i 和 j 就永远碰不了头,
// 进而 i >= j 的条件永远无法满足, 外层循环就成死循环了。
while (less(a[++i], v) && i < j-1) {}
while (less(v, a[--j]) && i < j-1) {}

if (i >= j) {
break;
}
exch(a, i, j);
}
exch(a, low, j);
return j;
}

注意,一定要保持 输入数组 元素顺序的随机性。此外,左侧扫描最好是在遇到 大于等于切分元素值的元素 时停下,右侧扫描最好是在遇到 小于等于切分元素值的元素 时停下。虽然这样可能会不必要地交换一些等值的元素,但在某些典型的应用中(处理只有若干种元素值的数组时),它能够避免算法的运行时间变为平方级别。

上面的实现有下面几点可以该改进:

  1. 切分操作中防止左端越界的测试条件 (j == low) 是冗余的,因为 j 为 low 时,前面的循环测试条件肯定通不过(a[low] 就是 v)。防止右端越界的测试条件 (i == high) 通过引入哨兵元素也可以去掉。

  2. 和大多数递归排序算法一样,快速排序的的性能改进基于以下两点:

    • 对于小数组,快速排序比插入排序慢;

    • 快速排序的 sort() 方法对于小数组也会递归地调用自己。

      对于小规模数组使用插入排序,就可以同时改进这两点。可是具体操作起来,对于多大的数组才合适用插入排序呢?这个参数的最佳值是和系统相关的,但是 5 ~ 15 之间的任意值在大多数情况下都能令人满意。

  3. 切分元素的选取。对于中等规模的数组,使用三取样选取切分元素;对于大规模数组,使用Tukey’s ninther 方法。三取样就是选 3 个元素作为样本元素,计算找到样本元素的中位数作为切分元素。Tukey’s ninther 方法就是选三组,每组三个元素,分别取三组元素的中位数,然后取三个中位数的中位数作为切分元素。

    注意,可以将切分元素放在数组末尾作为“哨兵”来去掉 partition() 方法中的数组右端边界测试 (i == high),算是对改进 1 的补充吧。

  4. 实际应用中经常会出现含有大量重复元素的数组,对于这些情况,上面的快速排序实现性能尚可,但还有巨大的改进空间。在有大量重复元素的情况下,快速排序的递归性会使 元素全部重复的子数组 经常出现,这儿就有很大的改进空间,我们可以将上面的实现的性能由线性代数级别提高到线性级别。

    一个简单的方法就是三向切分,把数组分成三部分,分别对应于小于、等于和大于切分元素的数组元素。但是在数组元素重复不多的普通情况下,它比标准的二分法多使用了很多次交换。Bentley-McIlroy 三向切分聪明地解决了这个问题,使得三向切分的快速排序 在包括有很多重复元素的实际应用中 比归并排序和其他排序方法更快。

简单三向切分的过程:

简单三向切分的示意图

简单三向切分的实现:

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

private void sort(Comparable[] a, int low, int high) {
if (high <= low) return;
// 将 a[low] 选定为切分元素
Comparable v = a[low];
// lt 是与切分元素相等的那部分的左边界,
// 因此其初始值就是 low
int lt = low;
// i 是还未确定所在区域的那部分的左边界。
// 因为已将 a[low] 选定为切分元素, 所以初始时
// 从下一个元素开始一直到子数组末尾都是未确定的区域
int i = low + 1;
// gt 是还未确定所在区域的那部分的右边界,
// 其初始值自然是 high
int gt = high;

// i..gt 还未确定所属区域的
// gt+1..high 比 v 大的
// lt..i-1 等于 v 小的
// low..lt-1 比 v 小的

while (i <= gt) {
int cmp = a[i].compareTo(v);
// 参与交换的两个元素的大小状况都很明确,
// 一个等于, 一个小于, 所以两个指针都要向前移动
if (cmp < 0) exch(a, lt++, i++);
// 参与交换的两个元素中, 交换到 i 位置的元素大小
// 不明确, 所以交换后 i 不能向前移动,
// 以便下一次处理刚交换到 i 位置的元素
else if (cmp > 0) exch(a, gt--, i);
else i++;
} // 现在 a[low..lt-1] < v=a[lt..gt] < a[gt+1..high] 成立

sort(a, low, lt-1);
sort(a, gt+1, high);
}

Bentley-McIlroy 三向切分的过程:

Bentley-McIlroy 三向切分的示意图

改进 2、3、4 的具体实现:

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

// cutoff to insertion sort, must be >= 1
private static final int INSERTION_SORT_CUTOFF = 8;

// cutoff to median of 3 partitioning
private static final int MEDIAN_OF_3_CUTOFF = 40;

@Override
public void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length-1);
}

private void sort(Comparable[] a, int low, int high) {
//if (high <= low) return; // unnecessary

int n = high - low + 1;

// 改进一: 对于小规模数组使用插入排序
if (n <= INSERTION_SORT_CUTOFF) {
insertionSort(a, low, high);
return;
}

// 改进二: 切分元素的选取
partition(a, low, high);

// 改进三: 使用 Bentley-McIlroy 3-way partitioning
// --------------------------
Comparable v = a[low];
int p = low, q = high+1;
int i = low, j = high+1;

while (true) {
while (less(a[++i], v)) if (i == high) break;
while (less(v, a[--j])) if (j == low) break;

// 如果 i 和 j 相遇, 且指向的元素等于 v,
// 就将其和最左边的那个小于 v 的元素交换位置。
// ++p 执行后 p 就指向最左边的那个小于 v 的元素,
// 交换位置后, p 就指向刚找到的这个等于 v 的元素。
if (i == j && eq(a[i], v)) {
exch(a, ++p, i);
}

if (i >= j) {
break;
}

exch(a, i, j);
if (eq(a[i], v)) {
exch(a, ++p, i);
}
if (eq(a[j], v)) {
exch(a, --q, j);
}
}

i = j+1;
for (int k = low; k <= p; k++) {
exch(a, k, j--);
}
for (int k = high; k >= q; k--) {
exch(a, k, i++);
}

sort(a, low, j);
sort(a, i, high);
// --------------------------
}

private void partition(Comparable[] a, int low, int high) {
int n = high - low + 1;

// use median of 3 as partitioning element
if (n <= MEDIAN_OF_3_CUTOFF) {
int m = median3(a, low, low + n / 2, high);
exch(a, low, m);
} else { // use Tukey ninther as partitioning element
int eps = n/8;
int mid = low + n/2;
int m1 = median3(a, low, low+eps, low+eps+eps);
int m2 = median3(a, mid-eps, mid, mid+eps);
int m3 = median3(a, high-eps-eps, high-eps, high);
int ninther = median3(a, m1, m2, m3);
exch(a, low, ninther);
}
}

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

private int median3(Comparable[] a, int i, int j, int k) {
return less(i, j)
? (less(j, k) ? j : (less(i, k) ? k : i))
: (less(k, j) ? j : (less(k, i) ? k : i));
}

算法性能评估

快速排序可能是应用最广泛的排序算法了。原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。

最引人注目的特点就是它是原地排序(只需要一个很小的辅助栈),且将长度为 N 的数组排序所需的时间和 $NlgN$ 成正比。另外,快速排序的内循环比大多数排序算法都要短小。

主要的缺点就是非常脆弱,在实现时要非常小心才能避免低劣的性能。

将长度为 N 的无重复数组排序,快速排序平均需要 ~ $2NlnN$ 次比较,以及 1/6 的交换。$2NlnN \approx 1.39NlgN$,也就是说平均比较次数只比最好情况多 39%。

快速排序最多需要约 $N^2/2$ 次比较,但随即打乱数组能够预防这种情况。

与其他算法相比较

总的来说,可以肯定的是对于大小为 N 的数组,快速排序的基本实现(二向切分)的运行时间在 $1.39NlgN$ 的某个常数因子的范围内。归并排序也能做到这一点,但是快速排序一般会更快。虽然它的比较次数多了 39%,但是它移动数据的次数更少。

答疑

问:随机地将数组打乱似乎占了排序用时的一大部分,这么做值得吗?
答:值得。这能够防止出现最坏情况,并且使得运行时间可以预计。它是一种(也是第一批)偏爱随机性的算法。Hoare 在 1960 年提出这个算法的时候就推荐了这种方法。

参考资源

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

归并排序-笔记

算法描述

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

  • © 2016-2020 Konglong
  • Powered by Hexo Theme Ayer
    • PV:
    • UV:

请我喝杯咖啡吧~

支付宝
微信