1.3.1 排序
1.3.1 排序
排序問題（sorting problem）要求我們按照升序重新排列給定列表中的數(shù)據(jù)項。當(dāng)然，為了讓這個問題有意義，列表中的數(shù)據(jù)項應(yīng)該能夠排序（數(shù)學(xué)家可能會說，這里需要一種全序關(guān)系）。在實踐中，我們常常需要對數(shù)字、字符和字符串的列表進(jìn)行排序，最重要的是，類似于學(xué)校維護(hù)的學(xué)生信息、圖書館維護(hù)的圖書信息以及公司維護(hù)的員工信息的記錄也需要按照數(shù)字或者字符的順序進(jìn)行排序。在對記錄排序的時候，我們需要選取一段信息作為排序的依據(jù)。例如，我們可以按照學(xué)生姓名的字母順序，也可以按照學(xué)號或者學(xué)生個人的平均分?jǐn)?shù)來對學(xué)生記錄進(jìn)行排序。這段特別選定的信息稱為鍵（key）。計算機(jī)科學(xué)家常常只關(guān)心如何對鍵的列表進(jìn)行排序，哪怕表中的元素不是記錄，也許僅僅是整數(shù)。
我們?yōu)槭裁葱枰行蛄斜砟兀渴紫龋行蛄斜砜赡苁撬蠼鈫栴}的輸出要求，例如對網(wǎng)上搜索結(jié)果進(jìn)行排序，或?qū)W(xué)生的平均成績進(jìn)行排序。其次，排序使我們更容易求解和列表相關(guān)的問題。其中最重要的是查找問題：這就是為什么字典、電話簿和班級名冊都是排好序的。在6.1節(jié)中我們將會看到一些例子來說明預(yù)排序列表的好處。同樣原因，在很多其他領(lǐng)域的重要算法（例如幾何算法和數(shù)據(jù)壓縮）中，排序也被作為一個輔助步驟。貪婪算法是本書后續(xù)章節(jié)將要討論的一個重要算法設(shè)計技術(shù)，它也要求有序的輸入。
到目前為止，計算機(jī)科學(xué)家已經(jīng)開發(fā)出了幾十種不同的排序算法。實際上，有人形象地把發(fā)明一種新的排序算法比喻為像設(shè)計一種更棒的捕鼠器那么困難。但我們很高興地告訴大家，尋找更好的“捕鼠器”這個行動還在繼續(xù)。這種百折不撓的精神是令人欽佩的，原因如下：一方面，有少數(shù)不錯的排序算法，只需要做大約n log2 n次比較就能完成長度為n的任意數(shù)組的排序；另一方面，沒有一種基于“鍵”值比較（相對比較鍵值的部分內(nèi)容而言）的排序算法能在本質(zhì)上超過它們。
排序領(lǐng)域有著那么多的算法，為什么還會出現(xiàn)這種困境呢？這不是沒有原因的。雖然有些算法的確比其他算法更好，但沒有一種算法在任何情況下都是最優(yōu)的。有些算法比較簡單，但速度相對較慢；另外一些速度比較快，但更復(fù)雜。有些算法比較適合隨機(jī)排列的輸入，而另一些則更適合基本有序的列表。有些算法僅適合排列駐留在快速存儲器中的列表，而另一些可以用來對存儲在磁盤上的大型文件排序，如此等等。
排序算法有兩個特性特別值得一提。如果一個排序算法保留了等值元素在輸入中的相對順序，就可以說它是穩(wěn)定的（stable）。換句話說，如果一個輸入列表包含兩個相等的元素，它們的位置分別是i和j，i<j，而在排好序的列表中，它們的位置分別為i'和j'，那么i' <j'肯定就是成立的。這種特性很有用，例如，有一個按照字母排序的學(xué)生列表，現(xiàn)在我們打算以學(xué)生個人的平均成績來排序：一個穩(wěn)定算法輸出的列表將會把成績相同的學(xué)生仍然按照字母順序排列。一般來說，將相隔很遠(yuǎn)的鍵交換位置的算法雖然不穩(wěn)定，但往往速度很快。在后面的章節(jié)中，一些重要的排序算法將會證實這一說法。
對于排序算法來說，第二個值得注意的特性是算法需要的額外存儲空間。如果一個算法不需要額外的存儲空間（除了個別存儲單元以外），我們就說它是在位的（in-place）。重要的排序算法有些是在位的，有些則不是。