動機
排序算法可利用不同資訊。插入排序受惠於近乎有序的輸入;隨機化快速排序避免固定輸入排列決定表現,但仍可能執行緩慢。計數與基數排序利用整數鍵結構,而非只透過比較取得次序。分析須說明所用優勢及其成本。
上一章已證明合併排序及比較下界。本章分析逆序對造成的移動成本、隨機性改變的複雜度陳述,以及按位排序為何需要穩定性。
定義
定義 8.1.1
(記錄、穩定性與逆序對)
輸入是記錄序列 ,其鍵取自全序集。正確的排序算法按鍵的非降序返回同樣的這些記錄。若鍵相等的記錄保持其原有的相對次序,則稱該排序是穩定的。逆序對是滿足 且 的一對位置。設 為此類位置對的個數;鍵相等的記錄對不構成逆序對。
最壞情況界適用於每一個容許的輸入和每一種隨機結果。隨機化算法的期望界是對固定輸入在其內部隨機選擇上取平均;它並不假設輸入本身是隨機抽取的。比較次數指鍵的比較次數。在下面使用的運算模型中,陣列存取、下標運算以及移動一個固定大小的記錄都視為常數代價的操作。
對於計數排序,鍵是 中的整數,其中 。對於基數排序,鍵有 個 進制數位,其中 ,必要時以前導零補齊。在此模型中,存取數位被假定為常數代價。這些假設是額外的資訊,並不是全序本身的推論。
定理/命題
定理 8.1.2
(插入排序對逆序對具有適應性)
僅當較前記錄的鍵嚴格大於被插入的鍵時才將其右移的插入排序是穩定且正確的。在陣列實作中,對 ,它恰好進行 次記錄移動,運行 次操作。其最壞情況代價為 ,而已經有序的輸入僅需 。
定理 8.1.3
(隨機化快速排序的期望比較次數)
假設 個鍵互不相同。每個遞歸子問題從其自身的記錄中均勻隨機地選取樞紐,劃分時將該樞紐與子問題中其餘每個記錄各比較一次。設 。對 ,鍵比較的期望次數為
因此,對 ,期望操作次數為 ,其中劃分工作量為線性。最壞情況仍為 。
定理 8.1.4
(穩定計數排序與最低位優先基數排序)
採用累計端點計數並從右向左掃描放置的計數排序是穩定且正確的,時間為 ,輔助空間為 。從最低位到最高位依次施行穩定的數位排序,可對定寬鍵排序。每個數位都使用計數排序時,時間為 ,輔助空間為 。
證明思路或證明
證明
(插入排序的正確性、穩定性與移動次數)
插入排序從左到右處理各位置。在插入下一個記錄之前,較前的前綴是原前綴的一個有序排列。將其中較大的鍵右移,直到被插入的鍵可以放在所有不超過它的鍵之後。此時前綴再次有序,且包含相同的記錄。歸納法證明其正確性。相等的鍵從不被移到彼此之後,這就證明了穩定性。
關於移動次數,可以把每次移動想像成被插入記錄與緊鄰其前且更大的記錄交換。對一個逆序的相鄰記錄對作相鄰交換,恰好消除一個逆序對。由於被交換的兩個記錄相鄰,它們與任何第三個記錄的關係都不會改變逆序對的總數。算法結束時沒有逆序對,所以移動的總次數恰好等於原來的逆序對個數。每一次成功的內層比較都導致一次移動;每次插入至多多出一次失敗的鍵比較。外層迭代與放置只增加線性的工作量,從而得到 的上下兩個界。
證明
(按名次對計算期望比較次數)
對於快速排序,用最終名次 標記這些互不相同的鍵。名次為 的兩個鍵被比較,當且僅當從名次 中最先被選為樞紐的是這兩個端點之一。該區間之外的樞紐無法將兩個端點分開。區間內部的樞紐會將它們永久分開;端點樞紐則直接比較它們。區間內每個鍵成為其首個樞紐的可能性相同,所以比較概率為 。
令指示變量在該對被比較時取一,否則取零。一對鍵至多被比較一次,因為比較之後其中一個記錄已作為樞紐被移出。期望的線性性(不要求各指示變量互相獨立)給出
積分界 說明了所述的漸近增長。反之,若每次都選取極端樞紐,則共有 次比較,所以二次的執行仍然可能出現。
證明透視
對哪一種隨機性取平均?
關鍵一步是按名次對計數,而不是跟著遞歸走:名次 的兩個鍵是否被比較,只取決於名次 之中哪一個最先被選為樞紐,因為區間之外的樞紐會把兩個鍵送到同一側。樞紐均勻選取,使這 個鍵各有相同機會最先被選中;鍵互不相同,使名次有定義,且每個樞紐都作嚴格劃分。然後由期望的線性性完成論證,並不需要各個鍵對事件之間相互獨立。
固定完整的輸入次序,只對樞紐的選擇取平均。鍵互不相同與樞紐均勻這兩個假設,保證了端點概率 ;它們不是計算中可有可無的細節。
證明
(計數排序與基數排序的正確性)
對於計數排序,首先統計每個鍵的頻數,並構造累計端點 ,即鍵不超過 的記錄個數。鍵 屬於分配給它的連續區塊。從右向左掃描輸入;將鍵為 的記錄放在輸出位置 ,然後將 減一。每次放置都使用該鍵區塊中最右邊仍為空的位置。所有記錄都被放入有序的區塊。在鍵相等的記錄中,原來最靠右的記錄被放在最右邊,因此保持了它們的次序。
對於基數排序,經過 趟穩定排序後,記錄已按其最低 位數位有序。下一趟對新的數位排序。在新數位相同的各組內,穩定性保持了先前低位的次序,於是記錄按最低 位數位有序。零趟時的斷言是空洞成立的;對所有數位進行歸納即證明正確性。時間與空間的界由各趟計數排序的代價相加並重複使用儲存空間得到。
例題詳解
例題 8.1.5
(四個逆序對,四次插入移動)
取鍵 ,下標用於區分鍵相等的記錄。第一個鍵大於其後三個鍵,給出三個逆序對;鍵二大於其後的 ,再給出一個。插入 時將三右移一次;插入二時將三右移一次;插入 時將三與二右移。四次移動得到 。嚴格比較使 仍在 之前,這除了說明有序之外,還展示了穩定性。
例題 8.1.6
(期望代價並非每次運行都能達到的代價)
對於三個互不相同的鍵,選到中間名次作樞紐的概率為 ,用兩次比較。選到極端名次的概率為 ,總共需要三次比較。因此期望為 ,與 相符。單次運行使用兩次或三次比較,絕不會恰為 次。這個非整數的期望描述的是對各次執行的平均,而不是一次執行中的分數工作量。
例題 8.1.7
(端點計數與反向放置)
對於鍵 ,鍵的全集為 ,頻數為 ,累計端點為 。反向掃描時,鍵一放在位置一, 放在位置三,零放在位置零, 放在位置二。輸出為 。若用同樣遞減的端點作正向掃描,則會使鍵二的兩個記錄顛倒次序,所以掃描方向是穩定性證明的一部分。
穩定性是記錄的可觀察性質
只顯示相等數值會掩蓋不穩定性,因為交換它們不改變顯示的數值序列。按原始位置區分記錄便可觀察穩定性。正確排序要求鍵有序,穩定性還要求記錄間的原有次序;前者不能推出後者。
穩定排序能保留次要鍵次序:若已按次要鍵排序,再按主鍵穩定排序,則每個主鍵組內的次序不變。最低位優先基數排序正是使用此機制;只保證每趟數位有序還不足以證明算法正確。
計數排序亦須統一下標。累計端點記錄個數,減一才得到從零開始的放置位置;遞減後表示該塊剩餘的可用位置。若從一開始編號,表達式不同而區塊不變量相同。混用約定會造成差一錯誤,這與頻數計數本身無關。
適應性、期望與最壞情況回答的是不同的問題
插入排序的逆序對界確定性地適用於實際輸入。若逆序對很少,那麼這一次具體的運行就很快。隨機化快速排序的期望界適用於每一個鍵互不相同的固定輸入,但它是對內部選擇取平均。罕見的糟糕樞紐序列仍可能很慢。兩個陳述互不蘊含,也都不改變最壞情況量詞的含義。
為了說明對樞紐規則的依賴,考慮有序輸入、總是選第一個記錄的規則,並要求劃分保持各遞歸部分內部的相對次序。每次劃分只使一個子問題縮短一個記錄。因此劃分的總工作量是一連串逐次變小的線性代價之和,呈二次增長。均勻隨機地選取樞紐可以防止該輸入排列每次都迫使同樣的壞劃分,但並不使壞劃分不可能發生。
期望時間定理也包含劃分所需的工作量。如果實作反覆低效地複製記錄,或者進行超線性的劃分工作,僅僅快速選出樞紐是不夠的。所述分析假定對每個子問題作一次線性掃描,且記錄與鍵的操作為常數代價。長字串、任意精度數或開銷高昂的比較函數,需要額外的代價模型。
鍵相等時需要不同的快速排序分析
精確的逐對公式假定鍵互不相同,因此每個記錄有唯一的名次,且每個樞紐都嚴格區分較小與較大的鍵。若所有鍵都相等,而二路劃分把所有非樞紐記錄送到同一側,則即使樞紐是隨機的,每次調用也可能只縮小一。樞紐的身份是隨機的,但其鍵沒有提供任何平衡資訊。鍵互不相同的定理不能用來宣稱這樣的執行是高效的。
三路劃分把鍵分為小於、等於和大於樞紐三部分,然後只對嚴格小於與嚴格大於的兩組遞歸。這樣就在一次線性劃分中處理了全部相等的輸入。要對任意重複度建立完整的期望界,需要專門的論證;目前的精確公式有意僅限於鍵互不相同的情形。這個例子指出了缺失的假設,而不是把重複鍵當作一個微小的實作細節。
反例模式
不穩定的數位排序會破壞先前的工作
取兩位數鍵十二和十一。按個位排序會使十一排在十二之前,它們的十位相同。如果容許十位這一趟顛倒數位相同的記錄,就會返回十二在前、十一在後,從而破壞所需的次序。穩定的最後一趟則保持低位的次序。僅有數位有序並不能證明一系列基數排序的趟是正確的。
為甚麼整數排序不違反比較排序下界
比較排序下界描述的是僅透過比較來得知次序的算法。計數排序讀取鍵值,並用它來選取計數陣列中的一項。這是對表示形式的額外存取。即使只出現少數鍵值,其時間也包含鍵全集的大小。因此,龐大而稀疏的鍵全集可能使計數排序比比較排序更差。
基數排序把表示形式的代價分攤到各數位上。其界包含數位個數與進制的大小;它並不是對每一個可能的整數輸入都簡單地為線性。增大進制會減少數位個數,但會增加每一趟都必須初始化的計數器個數。複雜度論斷必須同時保留這兩個參數以及數位存取的假設。
概念視角算法
比較界之前先選定模型
插入排序度量的是無序程度,快速排序對內部隨機性取平均,計數排序與基數排序則利用鍵的表示形式。相同的輸入長度並不能抹去這些不同的參數。在決定適用哪個定理之前,應當說明鍵的定義域、重複鍵的約定、記錄移動的代價以及隨機性。
常見錯誤
穩定的算法不一定快,快的算法也不一定穩定。同樣,期望界並不是對每個隨機種子的保證。對樞紐作隨機化,並不會自動使糟糕的重複鍵處理規則變得高效。
在逆序對分析中,應按原始位置統計鍵的嚴格不等式。鍵相等不產生逆序對。證明所統計的是已有記錄的移動次數,而不是包括存放被插入記錄在內的所有賦值。額外的放置已計入操作次數界的線性項中。
常見錯誤
(越過相等的鍵移動)
當前一個鍵大於或等於被插入的鍵時就移動,仍然得到有序的陣列,所以看似無害。對 並無逆序對,嚴格的插入排序不作任何移動;而這種弱比較會把 移動一次,返回 。於是移動次數超過 ,穩定性也隨之失去。
常見錯誤
(把計數排序當作對記錄數目是線性的)
其界是 ,只有當鍵的範圍 為 時才對 是線性的。對兩個鍵 與 ,有 而 ,計數排序為了排序兩條記錄,要初始化並掃描約一百萬個計數器。
總結
插入排序每個逆序對花費一次移動,並且在嚴格移動的條件下是穩定的。隨機化快速排序在鍵互不相同時的期望,源自名次區間端點的概率。計數排序使用有界整數鍵,其穩定的放置規則支撐了基數排序的歸納。每個界只有連同其輸入與運算模型一起才有意義。
練習
快速檢查
(計算鍵 (2a,2b,1a,1b) 中的逆序對個數,並給出插入排序的穩定輸出與移動次數。)
下標用於標識記錄,不影響其鍵。
解答 · 答案
鍵為二的兩個記錄中,每一個都大於其後鍵為一的兩個記錄中的每一個,共得到四個逆序對。鍵相等的記錄對不計入。穩定的插入排序輸出 ,並進行四次移動。它還要進行線性的外層迴圈與放置工作,所以僅移動次數並不是全部的操作次數。
快速檢查
(在對 個互不相同的鍵進行的隨機化快速排序中,求最小鍵與最大鍵被比較的概率,以及名次相鄰的兩個鍵被比較的概率。)
說明為甚麼這兩個答案可能相差很大。
解答 · 答案
對 ,最小與最大名次被比較,當且僅當其中之一是全部 個鍵中最先被選的樞紐,概率為 。相鄰名次構成大小為二的區間,所以其中一個端點必然是該區間中首個被選的樞紐,比較概率為一。居中的名次可以把相距較遠的鍵分開,而對於相鄰名次,在其中一個成為樞紐之前,沒有任何鍵能把它們分開。
快速檢查
(證明在有序且互不相同的輸入上,以第一個記錄為樞紐且劃分保持相對次序時恰用 次比較。解釋這為甚麼與隨機化的期望定理並不矛盾。)
寫出劃分比較次數之和,並指出被改變的假設。
解答 · 答案
保持相對次序的劃分使每個遞歸子問題仍然有序,所以其第一個記錄總是最小的鍵。各次劃分的規模為 ,分別貢獻 次比較。它們的和為 ,當 時為零。這個樞紐規則是確定性的,而不是在每個子問題內均勻選取。即使是隨機化算法也可能產生同樣的序列,但其定理是對所有樞紐選擇取平均,而不是用期望來界定每一次執行。