排序是本課程許多結構暗中依賴的問題:二分搜尋需要已排序的數據,而堆和平衡樹在某種意義上就是為了避免重複排序。前面關於鏈表合併排序的單元,示範了如何靠重新連結節點來合併與分割。本單元改為處理陣列,並回答三個問題:合併排序和快速排序為何正確、成本是多少,以及只靠比較鍵值的算法能否在漸進意義上優於 ?
定義
定義 18.2.1
(比較排序、穩定排序與原地排序)
比較排序接收序列 ,只能透過詢問所選位置是否滿足 來獲得鍵值資訊,並輸出按鍵值非遞減排列的一個置換。若鍵值相等的記錄保持輸入時的相對次序,排序便是穩定的;若除陣列外只用 額外儲存格,便是原地排序(對快速排序的遞歸堆疊,我們放寬為 )。除非另有說明,下文的成本 指長度為 的所有輸入中,鍵值比較次數的最壞情形。
陣列上的合併排序
合併排序先遞歸排序 的兩半,再經臨時陣列把兩半合併。
def merge_sort(a, lo, hi):
if hi - lo <= 1:
return
mid = (lo + hi) // 2
merge_sort(a, lo, mid)
merge_sort(a, mid, hi)
left, right = a[lo:mid], a[mid:hi]
i = j = 0
for k in range(lo, hi):
if j == len(right) or (i < len(left) and left[i] <= right[j]):
a[k] = left[i]; i += 1
else:
a[k] = right[j]; j += 1
定理 18.2.2
(陣列合併排序的正確性與成本)
對長度 的區段,merge_sort(a, lo, hi) 使該區段按非遞減次序排好,元素不變,且鍵值相等的記錄保持輸入次序。當 時,最壞情形的比較次數滿足 、,因此 。
證明
(對長度歸納,以及合併的不變量)
正確性。對長度 作歸納。長度不超過 1 的區段已排序。較長的區段中,兩半都嚴格較短,由歸納假設,兩次遞歸調用後它們已排序。合併迴圈的不變量是:寫入位置 之前,位置 按序存放兩半中最小的 個元素,而 left[i:] 與 right[j:] 中每個剩餘元素都不小於它們。由於兩個剩餘後綴各自已排序,取兩個首元素中較小者可保持此不變量。鍵值相等時取左邊的首元素,使排序穩定,因為左邊的記錄在輸入中先於右邊的記錄。每個元素都恰好被寫入一次,所以區段保持原有的元素。
成本。合併 個元素至多作 次比較,因為每次比較寫入一個元素,而最後一個元素無須比較便寫入。因此當 時,最壞情形滿足
逐層展開:第 層有 次大小為 的合併,每層少於 次比較,共有 層。故 ;對一般的 ,兩半的大小為 與 ,同一界在相差一個常數因子下仍成立。臨時陣列需要 個額外儲存格。
證明透視
合併不變量在哪裏用到排序與相等規則
歸納假設在合併中恰好用到一次:它說明 left 與 right 各自已排序,所以各自剩餘的首元素就是該半中最小的剩餘元素。兩個首元素中較小者因此是全部剩餘元素中最小的,這就是為甚麼寫入它能保持「每個剩餘元素都不小於已寫入的元素」。已寫入的前段保持有序,是因為每個被寫入的元素都不大於仍然剩餘的所有元素,特別是下一個被寫入的元素。
相等規則不影響有序性,只影響穩定性:當 left[i] == right[j] 時取左邊的首元素,使輸入中較早的左邊記錄排在右邊記錄之前。迴圈在 時完結:所有元素均已寫入,沒有剩餘後綴,不變量說明整個區段就是全部元素的有序排列。
快速排序
快速排序選一個樞紐,重排區段使較小的鍵在樞紐之前、較大的鍵在其後,再對兩側遞歸。
定義 18.2.3
(a[lo..hi] 的 Lomuto 分割)
取樞紐 ,並維持索引 ,初始為 。對 :若 ,便把 加 1,並交換 與 。最後交換 與 ,並回傳 。
迴圈不變量(在每個 值之前): 只含不大於 的鍵, 只含大於 的鍵,且 。結束時樞紐位於位置 ,其左側各鍵不大於 ,右側各鍵大於 ,所以它已在最終位置。
quicksort(a, lo, hi) 先作分割,再對 與 遞歸,其中 是回傳的索引。終止性:兩次調用的區段都嚴格短於原區段,因為樞紐被排除。正確性由歸納得出:分割後樞紐已在最終位置,而兩側由歸納假設排好序,且恰好含有應屬於該處的鍵。對 個元素分割恰好作 次比較。
定理 18.2.4
(快速排序的成本)
(a) 若樞紐總是所在區段的最小或最大鍵,快速排序作 次比較。(b) 若每個區段的樞紐均勻隨機選取,且鍵值互異,則期望比較次數至多為 。
證明
(最壞情形的遞推式,平均情形的指示概率)
(a) 的遞推式是 ,其和為 。以最後一個元素為樞紐時,已排序的陣列正好觸發這種行為。
(b) 把各鍵按排序後的次序記為 。兩個鍵至多被比較一次,因為比較必定涉及當前樞紐,而樞紐隨後被放到最終位置,不再參與。對 , 與 被比較,當且僅當 中最先被選為樞紐的是 或 :若先選中某個 的 ,它會永遠把兩者分到不同側。由對稱性,這 個鍵被最先選中的機會均等,故概率為 。由期望的線性性,
其中用到 。
概念視角結構
快速排序的樞紐構成一棵搜尋樹
把每個選出的樞紐當作一個節點,其左、右子節點分別是兩個遞歸調用所選的樞紐。較小的鍵值放左邊,較大的放右邊,所以這是鍵值上的一棵二叉搜尋樹。每次比較都是把一個樞紐與其區段內的鍵值配對,也就是與它的後代配對,而每一對祖先與後代恰好比較一次。因此比較次數等於所有節點深度之和(根的深度為 )。對已排序輸入、以最後一個鍵值作樞紐時,這棵樹是四個節點的鏈,深度之和為 ,與下面的例題一致。
除遞歸堆疊外,快速排序是原地的;若總是先對較小側遞歸、在較大側用迴圈,堆疊為 。它不是穩定排序。
下界
定理 18.2.5
(比較排序下界)
任何對 個互異鍵的所有輸入都正確排序的比較排序,在某個輸入上至少作 次比較。此外 ,因此最壞情形的比較次數為 。
證明
(數決策樹的葉子)
固定一個確定性算法與長度 。每次執行是一串比較,下一次比較只取決於先前的答案。這給出一棵二叉樹:內部節點是比較,邊是兩種答案,每片葉子是最終輸出的置換。 個互異鍵的不同輸入次序必須到達不同的葉子,因為一片葉子規定了唯一的重排方式,而兩種不同次序需要不同的重排才能排好序。輸入次序共有 種,所以至少有 片葉子。高度為 的二叉樹至多有 片葉子,故 ,即 。樹的高度就是最壞情形的比較次數。
漸進形式:,此乘積有 個因子,每個至少為 ,所以當 時 。
證明透視
葉子計數依賴的假設
這個論證只有一步關鍵:它不分析某個特定算法的行為,而是計算任何正確算法必須能產生多少種不同的結果。三個假設各在一處使用。確定性使下一次比較成為先前答案的函數,執行因而成為二叉樹中的一條路徑。對每個輸入都正確,迫使每片葉子指定唯一的重排,所以兩種不同次序不能共用一片葉子。鍵值互異才使 種次序需要 種不同的重排:若所有鍵值相等,任何重排都已是有序序列,所以這個計數對這類輸入沒有任何說明。
證明的結尾,是把葉子數 夾在兩個界之間:。之後把乘積折半,只是把 換成明確的形式 。
因此,合併排序在比較排序中漸進最優,而快速排序在期望意義上與之相當。此下界不適用於以其他方式檢視鍵值的算法,例如按數位計數的排序。
例題
例題 18.2.6
(八個鍵的合併排序)
排序 。兩半 與 先遞歸排序。前半中, 以 1 次比較變成 , 以 1 次比較保持不變;合併 與 時比較 、、,得 (3 次比較)。後半中, 與 各 1 次比較;合併時比較 、、,得 (3 次比較)。
最後合併 與 :比較 (取 1)、(相等,取左邊的 2)、(取右邊的 2)、(取 3)、(取 4)、(取 5)、(取 6)。此時右半已空,7 不經比較直接接上。輸出為 ,共 次比較。總計 。
例題 18.2.7
(一次 Lomuto 分割與小規模下界)
以樞紐 及 分割 。 時 ,(與自身交換)。 時 ,不變。 時 ,,交換位置 1 與 2:。 時 ,,交換位置 2 與 3:。 時 ,交換位置 3 與 4:。 時 ,交換位置 4 與 5:。 時 ,不變。最後交換位置 與 7:。樞紐在索引 5,左部 內部尚未排序(右部 恰好已有序),共用了 次比較。
當 時,下界給出 ,因為 。合併排序處理四個鍵至多用 次比較,所以最壞情形下沒有比較排序能做得更好。
例題 18.2.8
(已排序輸入上的快速排序,直至空區段)
取 ,以最後一個元素為樞紐。樞紐為 4 時, 的鍵都不大於 4,所以 每次都前進,每次交換都是與自身交換;最後一次交換也是與自身。分割在 3 次比較後回傳 。左側調用處理 ;右側調用處理 ,這是空區段,不作任何比較便立即返回。
在 上取樞紐 3 要 2 次比較,右側同樣為空;在 上取樞紐 2 要 1 次;單一鍵 要 0 次。總數為 ,與 (a) 的預測相符。每次分割都只剝掉樞紐本身,所以遞歸深度為 ,而每個右側調用都是空的。
細節與常見錯誤
反例模式
快速排序不穩定
以最後一個元素為樞紐,按鍵值排序 。兩個 2 都大於樞紐 1,迴圈從不交換,最後一步交換位置 0 與 2,得 。兩個相等的鍵次序被顛倒了。合併排序對同一輸入回傳 。
常見錯誤
(把期望界當成對所有輸入取平均)
界 是對算法自身隨機樞紐選擇取的期望,對每個固定輸入都成立。它不是對隨機輸入取的平均:固定的樞紐規則總有壞輸入,例如以最後一個元素為樞紐時的已排序輸入,5 個鍵要作 10 次比較。
常見錯誤
(把下界當成對每個輸入的界)
說的是長度為 的輸入中的最壞情形。它並不禁止某個特定算法對個別輸入(例如已排序的輸入)更快,也不適用於以比較以外方式檢視鍵值的算法。
常見錯誤
(在合併中使用嚴格比較)
若合併改用 left[i] < right[j] 而不是 left[i] <= right[j],鍵值相等時會先取右邊。左邊為 、右邊為 時,輸出是 ,穩定排序便不再穩定。有序性與比較次數都沒有改變,所以這個疏忽很容易被漏過。
習題與解答
快速檢查
(1. 以樞紐 5 對 [4,9,1,7,3,8,5] 作 Lomuto 分割。求最終陣列、樞紐索引與比較次數。)
解答 · 解答 1
時 ,。 時 9 不動。 時 ,,交換位置 1 與 2:。 時 7 不動。 時 ,,交換位置 2 與 4:。 時 8 不動。最後交換位置 3 與 6,得 。樞紐索引為 3,共 6 次比較。
快速檢查
(2. 以最後一個元素為樞紐的快速排序,對已排序陣列 [1,2,3,4,5] 作多少次比較?)
解答 · 解答 2
每次分割後所有元素都留在樞紐左側,因此各區段的大小依次為 5、4、3、2、1。分割共作 次比較,等於 。
快速檢查
(3. 對 6 個互異的鍵,比較排序必須能在某個輸入上使用的比較次數,最少是多少?)
解答 · 解答 3
是 。由於 ,在某個輸入上至少需要 10 次比較。
快速檢查
(4. 用歸納法證明:由 與 ,當 為 2 的冪時 。)
解答 · 解答 4
當 時,公式給出 。設公式對 成立,則 。由於 ,有 ,與上式相同。所以公式對 成立。
快速檢查
(5. 解釋為何決策樹論證需要 片葉子,而不只是每次比較有兩種結果。)
解答 · 解答 5
種輸入次序各自需要不同的重排才能排好序,所以兩種不同次序不能終止於同一片葉子。具有 片葉子的二叉樹,高度至少為 ,而 迫使高度至少為 ,即 。