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