排序是把記錄重排,使鍵值按非遞減次序排列。在學習快速排序與堆排序等高效算法之前,有兩種簡單方法值得精確理解:選擇排序與插入排序。它們是迴圈不變量、精確操作次數,以及穩定性與原地排序等詞彙的標準範例。成本分析沿用複雜度增長單元的模型:我們計算鍵值比較與元素移動,先寫成 的精確函數,再化簡為增長類別。
定義
若 ,陣列 稱為已排序。排序算法必須輸出輸入的一個已排序置換:沒有元素遺失、重複或被改動。若鍵值相等的記錄保持輸入時的相對次序,排序是穩定的;若除陣列外只用 個額外儲存格,則是原地排序。
定義 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,得 ,同樣顛倒。