插入排序與選擇排序的最壞情形需要二次時間。有兩個經典算法可在不使用大小為 的額外陣列下達到 :快速排序(quicksort)圍繞樞紐作分割;堆排序(heapsort)把陣列變成二叉堆,再反覆取出最大值。在「選擇與線性時間排序」單元討論的合併排序同樣是 且穩定,但需要第二個陣列。本單元證明快速排序與堆排序的正確性,推導其成本,並比較三者。它使用堆單元中的陣列表示法,以及複雜度單元的成本詞彙。
快速排序
快速排序排序 的方法是:選一個樞紐,重排區段使不大於樞紐的鍵在其前、較大的鍵在其後,再對兩側遞歸。
定義 3.4.1
(圍繞樞紐的分割)
以樞紐 對 作分割,是重排該區段並返回一個索引 (),使 , 的每個元素都不大於 , 的每個元素都大於 。此時位置 的元素已在最終排序位置上。
int partition(int a[], int lo, int hi) {
int p = a[hi];
int i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] <= p) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int q = partition(a, lo, hi);
quicksort(a, lo, q - 1);
quicksort(a, q + 1, hi);
}
}
分割不變量。在索引 的每次迭代開始時: 的每個元素都不大於 , 的每個元素都大於 ,且 。起初兩個區域皆為空。若 ,把 加 1 並交換 與 ,便把 放到第一個區域末端,而被擠出的較大元素移到第二個區域末端;若 ,第二個區域只是擴大。迴圈結束後,最後一次交換把 放到索引 ,其左側只有不大於它的鍵,右側只有較大的鍵。分割恰好作 次比較。
快速排序的正確性。對區段長度作強歸納。長度為 0 或 1 的區段無須處理。否則樞紐已在最終位置,兩個遞歸區段都嚴格較短,由歸納假設它們已排序,且恰好含有應位於各側的鍵。所以整個區段已排序。
定理 3.4.2
(快速排序的成本)
(a) 若每個樞紐都是所在區段的最小值或最大值,則對 個鍵的快速排序作 次比較。(b) 若每個區段被分成大小為 與 的兩部分,則比較次數滿足的遞推式解為 。(c) 若每個區段的樞紐均勻隨機選取且鍵值互異,則期望比較次數至多為 。
證明
(遞推式與逐對計數的論證)
(a) 的遞推式為 ,,其和為 。以最後一個元素為樞紐時,已排序的輸入(或反向排序、或全部鍵相等的輸入,因為測試是 )正好產生這種行為。(b) 的 有 層,每層少於 次比較。(c) 把各鍵按排序後的次序記為 。兩個鍵至多比較一次,因為比較涉及當前樞紐,而樞紐隨後不再參與工作。對 , 與 被比較,當且僅當 中最先被選為樞紐的是 或 :若先選中某個 的 ,兩者從此被分開。這 個鍵被最先選中的機會均等,故概率為 ,由期望的線性性,
證明透視
為甚麼逐對計數就能得到期望值
關鍵的一步是改為按鍵的配對來計算比較次數,而不是沿著遞歸樹追蹤。有兩件事使每一對的計數有明確意義:一對鍵至多被比較一次,因為比較涉及當前樞紐,而樞紐隨後不再參與運算,所以比較總次數就是每對一個指示變量之和;另外,兩個鍵會一直留在同一區段,直到某個樞紐落在它們之間的閉區間內,因此 被比較,當且僅當從 中最先被選為樞紐的是兩端之一。這裏用到鍵互不相同:若有相等的鍵,就不存在排序 ,而且測試 把樞紐的所有複本放到同一側,概率 便不再正確。隨機性只用了一次,就是使這 個鍵中每一個成為最先樞紐的機會均等。證明以期望的線性性收尾,它不要求不同的配對互相獨立,再配合調和級數的界 。若樞紐不隨機,(a) 部分表明固定的規則總有輸入使和大到 。
除遞歸深度外,快速排序是原地的;在情形 (a) 中遞歸深度可達 ,若先對較小一側遞歸、對較大一側用迴圈,深度便以 為界。它不穩定。
概念視角結構
遞歸樹就是二叉搜尋樹
把每個選出樞紐的調用記作一個節點,兩個遞歸調用分別是它的左、右子樹。鍵互不相同時,這棵樹是鍵上的二叉搜尋樹,因為一次調用的樞紐介於它兩側各鍵之間。分割時,區段內其餘每個鍵都與樞紐比較一次,所以每個鍵恰好與它的每個真祖先各比較一次,比較總次數就是所有節點的深度之和(根的深度為 )。以三個鍵為例,樞紐為 時深度為 ,總和為 ;樞紐為 時樹是一條鏈,深度為 ,總和為 。最好情形是平衡樹,情形 (a) 的最壞情形則是一條鏈。均勻隨機的樞紐使這棵樹成為隨機二叉搜尋樹,情形 (c) 界定的正是它的期望總深度。
堆排序
堆排序使用儲存在從零開始的陣列中的最大堆:索引 的子節點為 與 ,每個鍵都不小於其子節點的鍵。(堆單元的最小堆用同樣方法會得到遞減次序。)
void sift_down(int a[], int i, int size) {
for (;;) {
int big = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < size && a[l] > a[big]) big = l;
if (r < size && a[r] > a[big]) big = r;
if (big == i) return;
int t = a[i]; a[i] = a[big]; a[big] = t;
i = big;
}
}
void heapsort(int a[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
sift_down(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
sift_down(a, 0, end);
}
}
sift_down(a, i, size) 假設 之下的兩棵子樹在 內都已是最大堆,並透過在較大子節點超過該鍵時與其交換,來修復 處的堆性質;每次交換使該鍵下降一層,所以至多 次交換。
正確性。第一個迴圈處理索引 到 0。索引 及以上都是葉子,自然是堆;處理索引 時,其子節點的子樹已是堆,所以 sift_down 使以 為根的子樹成為堆。迴圈結束後 是最大堆。第二個迴圈的不變量:在索引為 end 的迭代之前, 是最大堆,而 按序存放最大的 個元素。最大值在 ;把它換到位置 end 便擴展了已排序的後綴,而 sift_down 修復較短前綴上的堆,因為只有根改變了。
成本。第一個迴圈由自底向上建堆的論證,成本為 (大部分節點靠近葉子,下沉的層數很少)。第二個迴圈執行 次,每次下沉至多 層。總計最壞情形 ,原地,額外空間 。它不穩定。
| 算法 | 最壞情形比較次數 | 額外空間 | 穩定 |
|---|---|---|---|
| 快速排序 | ;隨機樞紐的期望為 | 堆疊(先遞歸較小一側) | 否 |
| 堆排序 | 否 | ||
| 合併排序(陣列) | 是 |
例題
例題 3.4.3
(對 [8, 3, 7, 1, 5, 2] 作快速排序)
以樞紐 2(最後一個元素)、 分割整個陣列。元素 8、3、7 都大於 2。 時 ,所以 ,交換位置 0 與 3:。 時 5 較大。放置樞紐:交換位置 與 5:,樞紐索引為 1(5 次比較)。左部 無須處理。右部位置 2 至 5,,樞紐 3:7、8、5 都大於 3,所以 保持為 1;交換位置 2 與 5 得 ,樞紐索引為 2(3 次比較)。再處理位置 3 至 5,,樞紐 7:8 大於 7; 時 ,,交換位置 3 與 4:;最後交換位置 4 與 5,得 ,樞紐索引為 4(2 次比較)。餘下的區段 與 無須處理。陣列在 次比較後排好序。
例題 3.4.4
(對 [4, 10, 3, 5, 1] 作堆排序)
建堆:,從 開始。索引 1 的鍵 10 有子節點 5 與 1,不需移動。 時,鍵 4 有子節點 10 與 3;與 10 交換:,然後索引 1 的 4 有子節點 5 與 1;與 5 交換:。這是最大堆。
排序階段。交換位置 0 與 4:;在大小為 4 的堆中下沉 1:較大的子節點是 5,交換;然後在索引 1,索引 3 的子節點為 4,交換:。交換位置 0 與 3:;在大小為 3 的堆中下沉:較大的子節點是 4,交換:。交換位置 0 與 2:;在大小為 2 的堆中下沉:子節點 1 較小,不動。交換位置 0 與 1:。結果為 。
例題 3.4.5
(三個相異鍵的期望比較次數)
取 ,鍵為 ,頂層樞紐隨機均勻選取。若樞紐是 (概率 ),分割作 次比較,兩側都是空的,所以成本為 。若樞紐是 或 (概率 ),分割作 次比較,剩下兩個鍵,還要再作一次比較,所以成本為 。期望值為 。
用逐對公式得到同一個值: 與 的 ,各以概率 被比較; 的 ,概率為 。總和為 。界 成立。邊界情形 :沒有配對,和為空,成本為 ,與遞歸的預期一致。
細節與常見錯誤
常見錯誤
(某些輸入族使樞紐規則失效)
以最後一個元素為樞紐並使用測試 <= 的快速排序,在已排序陣列上退化為 ,在 個鍵全部相等的陣列上也一樣:每個元素都進入左側區域,樞紐落在最後一個索引。隨機樞紐可防止壞輸入;它並不排除運氣不好的可能,只是令其概率很小。三數取中或三路分割較能處理大量相等的鍵。
常見錯誤
(堆排序不穩定)
排序 :建堆時比較 與 ,因不是嚴格較大而不交換;第一次取出時交換位置 0 與 1,得 。相等的鍵次序被顛倒。
反例模式
建堆必須從最後一個內部節點向上進行
斷言:既然 sift_down 在一個索引上修復堆性質,那麼依 遞增次序調用它,同樣能建成堆。這是錯的,因為 sift_down(a, i, size) 要求 之下的兩棵子樹都已是堆。取 ,,索引為 與 。在 時,以索引 為根的子樹是 帶子節點 ,並不是堆,前置條件不成立。調用比較子節點 與 ,把 與 交換,得 ;接著 把 與其子節點 交換,得 。根 小於其子節點 ,所以這不是最大堆,排序階段便會取出錯誤的最大值。正確次序下,先 得 ,再 把 先與 交換、再與 交換,得堆 。修正辦法就是建堆階段的向下迴圈,它保證每次調用前子節點的子樹已是堆。
習題與解答
快速檢查
(1. 以樞紐 5(最後一個元素)對 [6,2,9,4,7,1,5] 作分割。求結果陣列、樞紐索引與比較次數。)
解答 · 解答 1
:。:,,交換位置 0 與 1:。:。:,,交換位置 1 與 3:。:。:,,交換位置 2 與 5:。最後交換位置 3 與 6:。樞紐索引為 3,共 6 次比較。
快速檢查
(2. 此快速排序對四個相等的鍵 [7,7,7,7] 作多少次比較?)
解答 · 解答 2
每個元素都滿足 ,所以 每次都前進,樞紐落在最後一個索引。各區段的大小為 4、3、2、1,所以比較次數為 ,即 時的最壞情形 。
快速檢查
(3. 以堆排序的建堆迴圈,由 [2,9,7,6,5,8] 建立最大堆,並給出陣列。)
解答 · 解答 3
,從 開始。鍵 7 只有索引 5 的子節點(鍵 8):交換,得 。:鍵 9 的子節點為 6 與 5,不變。:鍵 2 的子節點為 9 與 8;與 9 交換:;在索引 1,鍵 2 的子節點為 6 與 5;與 6 交換:。索引 3 沒有子節點。堆為 。
快速檢查
(4. 對堆 [9,6,8,2,5,7] 執行排序階段的第一步取出,並給出之後的陣列與堆大小。)
解答 · 解答 4
交換位置 0 與 5:。堆現在佔據索引 0 至 4。下沉 7:子節點為 6 與 8,較大者是 8,所以交換:。索引 2 的子節點在索引 5 與 6,超出大小為 5 的堆,於是停止。陣列為 ,堆大小為 5。
快速檢查
(5. 為何堆排序的建堆階段雖然調用約 次下沉,成本卻只有 ?)
解答 · 解答 5
在高度為 的節點處調用,至多作 次交換。 個節點的堆中,高度為 的節點至多有 個,所以總成本至多為 ,因為 。因此建堆階段需要 ,而不是 。