《编程珠玑》第 11 章──排序

已有的排序方法使用起来可能比较麻烦,或者速度太慢以至于无法解决特定问题。

插入排序

1
2
3
4
5
6
7
for (int i = 0; i < n; ++i) {
for (int j = i; j > 0 && l[j - 1] > l[j]; --j) {
int tmp = l[j];
l[j] = l[j - 1];
l[j - 1] = tmp;
}
}

然后可以把对 tmp 的赋值语句移出内循环。

1
2
3
4
5
6
7
8
for (int i = 0; i < n; ++i) {
int tmp = l[i];
int j = 0;
for (j = i; j > 0 && l[j - 1] > tmp; --j) {
l[j] = l[j - 1];
}
l[j] = tmp;
}

快速排序

只有一个划分,划分方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void qsort1(int l, int u) {
if (l >= u) {
return;
}
int m = l;
for (int i = l + 1; i <= u; ++i) {
if (x[i] < x[l]) {
swap(++m, i);
}
}
swap(l, m);
qsort1(l, m - 1);
qsort1(m + 1, u);
}

第二种就是从后往前遍历,这样不需要第二个 swap

1
2
3
4
5
6
7
8
9
10
11
12
13
void qsort2(int l, int u) {
if (l >= u) {
return;
}
int m = u;
for (int i = u - 1; i >= 0; --i) {
if (x[i] >= x[l]) {
swap(--m, i);
}
}
qsort2(l, m - 1);
qsort2(m + 1, u);
}

第三种就是用 ij 划分数组的两端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void qsort3(int l, int u) {
if (l >= u) {
return;
}
int tmp = x[l];
int i = l;
int j = u + 1;
while (1) {
do { i++; } while (i <= u && x[i] < tmp);
do { j--; } while (x[j] > tmp);
if (i > j) {
break;
}
swap(i, j);
}
swap(l, j);
qsort3(l, j - 1);
qsort3(j + 1, u);
}

第四种就是随机选一个标杆数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void qsort4(int l, int u) {
if (l >= u || l < 0) {
return;
}
int tmp = rand() % (u - l + 1) + l;
swap(l, tmp);
tmp = x[l];
int i = l;
int j = u + 1;
while (1) {
do { i++; } while (x[i] < tmp && i <= u);
do { j--; } while (x[j] > tmp);
if (i > j) {
break;
}
swap(l, j);
}
swap(l, j);
qsort4(l, j - 1);
qsort4(j + 1, u);
}

习题

1

就像其他任何强大的工具一样,我们经常会在不该使用排序的时候使用排序,而在应该使用排序的时候却不使用排序。请解释在计算 n 元浮点数组的最小值、最大值、均值、中值、众数等统计量时,哪些情况会导致过度使用排序,哪些情况会导致不能充分利用排序。

最大值或者最小值都不需要排序。不用排序也可以得到中位数,第 9 题便是这个问题。排序对众数比较有效。对于浮点数的求均值,先排序会提高精度。

2

[R.Sedgewick]把 x[l] 用作哨兵以加速 Lomuto 的划分方案。说明如何利用该方法来移除循环后面的 swap。

如上的 qsort2 函数。

4

虽然快速排序平均只需要 O(log n) 的栈空间,但是在最坏情况下需要线性空间,请解释原因。修改程序,使得最坏情况下仅使用对数空间。

每次选中的标杆数都是最大值或者最小值,那么就是线性空间。为了使得最坏情况下,栈空间不是线性,那么要保证每次能够对半分,所以标杆数应该是中位数。所以先用 O(n) 的时间找到中位数。这样的话,时间复杂度也不会增加。

5

[M.D.McIlroy]说明如何用 Lomuto 的划分方案来排序可变长的位字符串,要求排序时间与位字符串的长度之和成正比。

按照长度,把小于该长度的放到左边,大于的就放到右边。然后递增长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
void bsort(l, u, depth)
if l >= u
return
for i = [l, u]
if x[i].length < depth
swap(i, l++)
m = l
for i = [l, u]
if x[i].bit[depth] == 0
swap(i, m++)
bsort(l, m-1, depth+1)
bsort(m, u, depth+1)

6

使用本章的方法实现其他排序算法。选择排序首先将最小的值放在 x[0] 中,然后将剩下的最小值放在 x[1] 中,依此类推。希尔排序(或“递减增量排序”)类似于插入排序,但它将元素向后移动 h 个位置而不是 1 个位置。h 的值开始很大,然后慢慢减小。

1
2
3
4
5
6
7
8
9
10
11
12
void selectsort(int u) {
if (u <= 1) {
return;
}
for (int i = 0; i <= u - 1; ++i) {
for (int j = i + 1; j <= u; ++j) {
if (x[j] < x[i]) {
swap(i, j);
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shellsort(int n) {
int h = 1;
while (h < n) {
h = 3 * h + 1;
}
while (h >= 1) {
h /= 3;
for (int i = h - 1; i <= n - 1; ++i) {
for (int j = i + 1; j >= h && x[j] < x[j - h]; j -= h) {
swap(j - h, j);
}
}
}
}

9

编写程序,在 O(n) 时间内从数组 x[0..n-1] 中找出第 k 个最小的元素。算法可以对 x 中的元素进行排序。

利用快速排序的思想,使得 j 两边的数字分别小于 x[j] 和大于 x[j]。然后比较 j 和 k 的大小,就知道还要对左边或者右边继续划分。其实求中位数就是这个方法的特例,这个思维用在 Leetcode 上的 Median of Two Sorted Arrays,这样的话该题目的时间复杂度就是最低的 O(m+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
void select1(int l, int u, int k) {
if (l >= u) {
return;
}
int tmp = rand() % (u - l + 1) + l;
swap(l, tmp);
tmp = x[l];
int i = l;
int j = u + 1;
while (1) {
do { i++; } while (x[i] < tmp && i <= u);
do { j--; } while (x[j] > tmp);
if (i > j) {
break;
}
swap(l, j);
}
swap(l, j);
if (j == k) {
printf("%d\n", x[j]);
return;
} else if (j < k) {
select1(j + 1, u, k);
} else {
select1(l, j - 1, k);
}
}

11

编写一个“宽支点”划分函数,使得结果如下“图所示:如何将这个函数应用到快速排序中?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct location {
int x;
int y;
};

struct location *qsort5(int l, int u) {
struct location *result = malloc(sizeof(struct location));
// [x, y]
result->x = l;
result->y = l;
for (int i = l + 1; i <= u; ++i) {
if (x[i] < x[l]) {
swap(++(result->x), i);
swap(++(result->y), i);
} else if (x[i] == x[l]) {
swap(++(result->y), i);
}
}
swap(l, result->x);
return result;
}

14

本章的快速排序使用两个整数下标表示子数组。在 Java 等语言中必须这样做,因为它们没有指向数组的指针。在 C 或 C++ 中,可以为初始调用和所有的递归调用使用类似下面的函数来排序整数数组:

1
void qsort(int x[],int n)

修改本章中的算法,使它们都使用这一接口。

数组的指针直接加上偏移量就可以得到 x[j] 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void new_swap(int a, int b, int *y) {
int tmp = y[a];
y[a] = y[b];
y[b] = tmp;
}
void qsort1_1(int x[], int n) {
int i, j;
if (n <= 1) {
return;
}
for (i = 1, j = 0; i <= n; ++i) {
if (x[i] < x[0]) {
new_swap(++j, i, x);
}
}
new_swap(0, j, x);
qsort1_1(x, j);
qsort1_1(x + j + 1, n - j - 1);
}