排序是把记录重排,使关键字按非递减次序排列。在学习快速排序与堆排序等高效算法之前,有两种简单方法值得精确理解:选择排序与插入排序。它们是循环不变量、精确操作次数,以及稳定性与原地排序等概念的标准示例。代价分析沿用复杂度增长单元的模型:我们计算关键字比较与元素移动,先写成 的精确函数,再化简为增长类别。
定义
若 ,数组 称为有序。排序算法必须输出输入的一个有序置换:没有元素丢失、重复或被改动。若关键字相等的记录保持输入时的相对次序,排序是稳定的;若除数组外只用 个额外存储单元,则是原地排序。
定义 3.3.1
(逆序对)
的一个逆序对是一对下标 ,满足 。令 为逆序对的个数。数组有序,当且仅当 ;最大可能值为 ,在严格递减的数组上取到。
选择排序
选择排序反复从未排序的后缀中选出最小值,逐步建立有序的前缀。
void selection_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int m = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[m]) m = j;
int t = a[i]; a[i] = a[m]; a[m] = t;
}
}
不变量。在下标为 的一趟开始之前,前缀 按序存放数组中最小的 个元素,且 的每个元素都不小于前缀中的任何元素。起初前缀为空。每一趟中,内层循环找出 的一个最小值所在位置 ;把它换到位置 ,前缀多了一个元素,不变量仍然成立。 的一趟结束后,前 个位置已是最终位置,最后一个元素必然最大,所以数组已有序。置换性质成立,因为唯一的改动是交换。
代价。第 趟内层循环作 次比较,与数据无关,所以比较次数恰好为
交换至多 次。因此选择排序在任何情形下比较次数都是 ,但移动很少,在移动记录代价高昂时有用。它是原地的,但不稳定:排序 (字母标示身份)时,位置 0 与位置 2 交换,得 ,相等的关键字次序被颠倒。
插入排序
插入排序维护一个有序的前缀,把下一个元素插入其中。
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
不变量。在下标为 的迭代开始之前,前缀 是原来元素 的一个有序重排。while 循环把每个大于 key 的元素右移一格,所以停止时,位置 的空位在所有不大于 key 的元素之后、较大元素之前;在该处写入 key,就使 有序且元素不变。 完成后整个数组有序。循环会终止,因为 递减,且 的测试守住左边界。
由于移动使用严格比较 >,元素不会越过与它相等的元素,所以插入排序是稳定的,也是原地的。
定理 3.3.2
(移动次数等于逆序对数)
插入排序对 所作的移动(执行 a[j + 1] = a[j])总次数等于 。关键字比较次数至少为 ,至多为 。
证明
(按右端下标计算移动次数)
在第 次迭代中,被移动的元素恰好是 中严格大于 的那些,因为前缀有序,而循环在第一个不大于 key 的元素处停止。它们的个数就是右端下标为 的逆序对 ()的个数。对 求和,每个逆序对恰好被计算一次。每次迭代对每次移动作一次比较,再加上至多一次不成立的比较(若循环在左边界停止则没有),由此得出比较次数的界。
证明透视
有序前缀与严格测试用在哪里
这个论证只用了一次不变量和一次严格不等式。不变量(前缀 有序)使一次向左扫描就能确定整个集合 :扫描在第一个不大于 key 的元素处停止,而有序保证更左边的元素也都不更大,所以停止点之后不会藏着更大的元素。没有它,结论不成立:若前缀无序,例如 ,key 为 ,扫描比较 不成立便停止,没有任何移动,但 是逆序对。严格测试是第二个假设:与 key 相等的元素不被移动,而相等的一对不是逆序对,所以程序与定义使用同一个严格不等式。证明的收尾是按右端下标 把逆序对分类:每个逆序对恰好属于一次迭代,所以各次迭代的计数相加得 ,没有重复。
因此,在有序数组上代价是 ( 次比较,没有移动),在严格递减数组上是 ( 次移动),一般情形为 ,所以输入接近有序时很快。
概念视角组合
把逆序对看成相邻交换
交换两个相邻元素 ,只有这一对的相对顺序改变,所以 恰好减少 。有序数组的 ,因此任何只靠交换相邻元素来排序的方法,至少需要 次交换;而 的数组恰好可以用 次相邻交换排好。插入排序正好达到这个下界:把关键字向左移过 个更大的元素,相当于 次相邻交换,但实际只做 次移位和最后一次写入,不必做 次完整交换。所以,移位次数就是输入中顺序颠倒的元素对的个数。
例题
例题 3.3.3
(对 [29, 10, 14, 37, 13] 作选择排序)
第 0 趟:整个数组的最小值是下标 1 的 10;与下标 0 交换,得 (4 次比较)。第 1 趟: 的最小值是下标 4 的 13;与下标 1 交换:(3 次比较)。第 2 趟: 的最小值是下标 2 的 14,已在原位,交换不产生变化(2 次比较)。第 3 趟: 的最小值是下标 4 的 29;交换:(1 次比较)。总共 次比较,有效交换三次。
例题 3.3.4
(对 [5, 2, 4, 6, 1, 3] 作插入排序)
,key 为 2:与 5 比较(较大),右移,然后左边界使循环停止:(1 次比较,1 次移动)。,key 为 4:5 较大,右移;2 不大于 4,停止:(2 次比较,1 次移动)。,key 为 6:5 不大于 6,不移动(1 次比较)。,key 为 1:与 6、5、4、2 比较,全部较大,所以移动四次,由左边界停止循环:(4 次比较,4 次移动)。,key 为 3:6、5、4 较大,被右移;2 不大于 3:(4 次比较,3 次移动)。
移动共 次。 的逆序对为:5 与 2、4、1、3(四个);2 与 1(一个);4 与 1、3(两个);6 与 1、3(两个);共 个,与定理吻合。比较共 次。
例题 3.3.5
(含相等关键字与极小数组的插入排序)
对 排序,其中 、 是关键字相等但身份不同的元素。:key 为 ,小于 ,所以 右移,左边界使循环停止:(1 次比较,1 次移动)。:key 与 比较,测试 不成立,没有移动(1 次比较,0 次移动)。:key 为 ,与 、 比较,两者都较大,都被右移;然后 不成立,循环停止:(3 次比较,2 次移动)。相等的关键字保持 的次序,符合稳定性的要求。
的逆序对是 、、,共 个;移动共 次。 不是逆序对,因为两个关键字相等。比较共 次,介于 与 之间。边界情形 与 :循环 for (i = 1; i < n; ...) 一次也不执行,没有比较、没有移动,而数组本来就有序。
细节与常见错误
常见错误
(更改比较方式会破坏稳定性)
若插入排序的 while 测试写成 a[j] >= key,相等的元素会互相越过。对 ,,key 为 ,测试 成立,于是 右移, 被写到前面:。严格的 > 才使排序稳定。
常见错误
(交换次数少不代表更快)
选择排序至多作 次交换,但比较总是 次,所以在有序的输入上,它的比较次数远多于插入排序。何者更佳,取决于比较与移动何者是主要代价,以及输入的混乱程度。
反例模式
把最小值交换到位并不稳定
断言:选择排序只作交换,从不直接交换两个相等的关键字,所以相等的关键字会保持原来的次序。这是错的。对 执行上面的程序:第 趟,扫描先令 ,发现 不成立,再发现 成立,令 ;交换后得 。第 趟发现 不成立,所以 与自己交换。输出 虽已有序,却颠倒了相等的关键字:长距离的交换把 带过了 。修正方法是不用交换,而把 整体右移一格,再把最小值放到位置 ,并取最左边的最小值(严格测试 a[j] < a[m] 已做到)。对同一输入得 ,是稳定的;代价是每趟最多 次移动,失去“至多 次交换”的优势。
习题与解答
快速检查
(1. 选择排序对 100 个元素作多少次比较?交换至多多少次?)
解答 · 解答 1
无论输入如何,比较恰好 次,交换至多 次,每趟一次。
快速检查
(2. 数出 [3,1,4,2] 的逆序对,并说明插入排序作多少次移动。)
解答 · 解答 2
逆序对为 、、,所以 。插入排序恰好作 3 次移动:key 1 移动 3(一次),key 4 不移动,key 2 移动 4 与 3(两次)。
快速检查
(3. 求插入排序对 [1,2,3,4,5] 与 [5,4,3,2,1] 的比较与移动次数。)
解答 · 解答 3
对 ,4 次迭代各作一次比较、没有移动:4 次比较,0 次移动。对 ,第 次迭代移动前面全部 个元素,并由边界停止,所以作 次比较与 次移动:共 次比较与 次移动,等于 。
快速检查
(4. 陈述并证明说明选择排序正确的不变量。)
解答 · 解答 4
不变量:第 趟之前, 有序,且其每个元素都不大于 的任何元素。 时前缀为空。第 趟中,元素 是 的最小值,所以它不小于前缀的元素,也不大于后缀其余元素;把它换到位置 即扩展了有序前缀,被换出的元素仍留在后缀中,所以条件依然成立。到 时,前缀有 个元素,各自不大于剩下的唯一元素,所以整个数组有序。
快速检查
(5. 用例子说明选择排序不稳定,以及使用非严格测试的插入排序不稳定。)
解答 · 解答 5
对 作选择排序:最小值 1 在下标 2;与下标 0 交换得 ,相等的关键字次序颠倒。对 以测试 a[j] >= key 作插入排序:key 为 ,且 ,所以 右移, 被写在下标 0,得 ,同样颠倒。