《算法基礎：打開算法之門》一第3章 排序算法和查找算法

本節書摘來自華章出版社《算法基礎：打開算法之門》一書中的第3章，作者 ［美］托馬斯 h 科爾曼（thomas h cormen），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

algorithms unlocked

排序算法和查找算法

在第2章中，我們看到了在數組上進行線性查找的三個算法。我們能做得更好嗎？答案是：看情況。如果不清楚數組中的元素是否有序，我們是不可能做得更好的。在最壞情況下，我們必須查找數組的所有n個元素，因為如果在前n-1個元素中不能找到要找的值，那麼要查找的元素可能在第n個位置上。是以，當我們不清楚數組中的元素是否有序時，我們不可能實作比Θ（n）更好的最壞情況運作時間。

然而，假定數組是以非遞減順序排序的，那麼根據“非遞減”的含義得出每個元素均小于或者等于它的後繼。在這一章中，我們會看到當數組有序時，能夠使用二分查找的簡單技術來實作從包含n個元素的數組中查找元素的時間複雜度為o（lgn）的算法。正如第1章提到的，與n相比，lgn增長更緩慢，是以二分查找法在最壞情況下會優于線性查找。

如果你是一個非計算機專業人士，同時你未閱讀14節，那麼你應該回過頭去閱讀關于對數的那部分内容。

一個元素比另一個元素小意味着什麼呢？當元素是數字時，結果是顯然的。當元素是字元串時，我們會聯想到字典序：如果在字典中某元素出現在另一個元素的前面，那麼該元素就小于另一個元素。當元素是其他形式的資料時，我們必須自定義“小于”的含義。隻要對“小于”有了清晰的概念，我們就能判定數組是否是有序的。

回憶第2章中在書架上查找書的例子，我們能将書籍按照作者名排序，也可以按照書名排序，如果書籍陳列在圖書館中，那麼也可以按照索書号排序。在本章中，如果書籍是按照作者名的字母序從左到右排序，25則稱書架上的書籍是有序的。然而，書架上也可能包含由同一個作者寫的多本書，比如你有好幾本由莎士比亞寫的書。如果我們并非想要查找由莎士比亞所寫的任意一本書，而是某本特定的書，那麼如果兩本書有相同的作者，我們就假定這兩本書是按照書名的字母序從左到右排序。再或者，如果我們關心的僅僅是作者的名字，那麼當進行查找的時候，任何一本由莎士比亞所寫的書均可以作為我們要查找到的最終結果。我們稱要比對的資訊為關鍵字。在書架的例子中，關鍵字是作者的名字，而不是作者名和書名的組合，後者是為了處理同一個作者有兩部作品的情況。

那麼，我們如何才能獲得排好序的數組呢？這一章中，我們将看到4個算法——選擇排序、插入排序、歸并排序和快速排序——為了将一個數組排好序，我們要将其中一個算法應用到我們所講的書架這個例子上。每種排序算法都有優點和缺點，在本章最後我們将回顧和比較這些排序算法。在本章中我們要學到的所有算法在最壞情況下的運作時間或者等于Θ(n2)，或者等于Θ(nlogn)。是以，如果僅僅需要執行幾個查詢，你最好直接執行線性查找。但是如果你将進行多次查找，那麼最好先将數組排序，然後執行二分查找算法。

排序本身就是一個重要的問題，而不僅僅是二分查找的預處理步驟。考慮所有需要排序的資料，例如電話簿需要按照名字排序；每月銀行對賬單支票或者需要按照支票号排序，或者需要按照銀行處理賬單的日期排序；甚至由網絡搜尋引擎搜尋的結果也需要按照與查詢的相關性進行排序等。而且，排序通常是其他算法中的一個步驟。例如，在計算機圖形學中，對象往往會互相層疊在一起。這時需要這樣一個程式：它能夠将螢幕上的對象按照“上方”關系排序以便能夠實作按照從底部到頂部的順序依次繪制對象。

在繼續講述前，還需說明我們要對什麼進行排序。除了關鍵字（進行排序時，我們将其稱為排序關鍵字）之外，通常我們将排序過程中的剩餘元素稱為衛星資料（satellite data）。盡管衛星資料可能來自衛星，但是通常它并非來自衛星。衛星資料是和排序關鍵字關聯的資訊，在重排元素時，衛星資料也需要随着關鍵字進行重排。例如書架這個例子，排序關鍵字是作者的名字，而衛星資料就是書本身。

我以下面這種方式給學生們解釋衛星資料的含義，以保證他們能明白該詞。我将學生的等級成績儲存至一份電子資料表中，26其中每行是按照學生的名字排序的。為了得出學期末的最終課程成績，我重排了行，此時排序關鍵字是包含着學生課程分數的那一列，而其餘列（包含學生姓名）均被稱作衛星資料。我将分數按照降序排列，是以位于頂部的那些行的成績為a，而靠近底部的那些行的分數為d或者e。

dartmouth使用e而不是f來表示不及格的成績。我不清楚為什麼這樣表示，但是通過将字母形式的等級成績轉化為四維的數值型等級成績，而不是五維的，我猜測如此能更加簡化計算機程式。

假設我僅僅重排了包含分數的那一列，而沒有重排包含分數的整行，那麼最終結果是學生姓名依然是按照字母順序排序的。這就會讓名字排在字母表前面的學生因為他們的分數高而很開心，而名字排在字母表後面的學生因他們的分數低而不開心了。

以下是關于排序關鍵字和衛星資料的其他例子。在電話簿中，排序關鍵字是名字，而衛星資料是位址和電話号碼。在銀行對賬單中，排序關鍵字是支票号碼，而衛星資料包含支票金額和标注的交易日期。在搜尋引擎中，排序關鍵字是查詢的相關性的評估結果，而衛星資料是網頁的網址，再加上搜尋引擎所存儲的跟該網頁相關的其他資料資訊。

本章中我們針對數組進行讨論，同時假定每個元素僅僅包含一個排序關鍵字。如果要實作下述的任意一個排序算法，你一定要確定當重排元素時，相應的衛星資料也要進行相應的重排操作，或者保證當重新排序關鍵字時，指向衛星資料的指針要做相應的變換。為了将書架模拟為計算機數組，我們需要假定書架和書需要滿足兩個額外的特性，我承認這點不太切合實際。首先，書架上的所有書大小規格一樣，因為在計算機數組中，數組中的所有項占用相同的空間大小。其次，我們能按照書架上書的位置對其從1到n進行編号，并且我們将每一個站位稱為一個位置。位置1是最左側的位置，而位置n代表最右側的位置。正如你可能猜到的，書架上的每個位置均相應地對應着數組中的一項。

我也想說說“排序”（sorting）這個詞。27一般意義上的排序和我們在計算使用中的排序的含義不同。我電腦中的線上詞典上是這樣定義的，“組内系統地整理；根據類型或者類别分類等”：例如你可能這樣“排序”你的衣物，襯衫放在一個地方，褲子統一放在另一個地方，等等。在計算機算法領域中，排序意味着按照一個明确定義的順序排列，此時“組内系統地整理”也稱為“分桶”（bucketing）、“桶狀的”（bucketizing）或者“裝箱”（binning）等。