排序就是將一組對象按照某種邏輯順序重新排列的過程。比如，信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期，大家普遍認(rèn)為30%的計算周期都用在了排序上。如果今天這個比例降低了，可能的原因之一是如今的排序算法更加高效，而并非排序的重要性降低了。現(xiàn)在計算機(jī)的廣泛使用使得數(shù)據(jù)無處不在，而整理數(shù)據(jù)的第一步通常就是進(jìn)行排序。所有的計算機(jī)系統(tǒng)都實(shí)現(xiàn)了各種排序算法以供系統(tǒng)和用戶使用。

即使你只是使用標(biāo)準(zhǔn)庫中的排序函數(shù)，學(xué)習(xí)排序算法仍然有三大實(shí)際意義：

1.對排序算法的分析將有助于你全面理解本書中比較算法性能的方法；

2.類似的技術(shù)也能有效解決其他類型的問題；

3.排序算法常常是我們解決其他問題的第一步。

更重要的是這些算法都很經(jīng)典、優(yōu)雅和高效。排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計算中有著重要的地位，它能夠應(yīng)用于事物處理、組合優(yōu)化、天體物理學(xué)、分子動力學(xué)、語言學(xué)、基因組學(xué)、天氣預(yù)報和很多其他領(lǐng)域。其中一種排序算法（快速排序）甚至被譽(yù)為20世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。

我們將學(xué)習(xí)幾種經(jīng)典的排序算法，并高效地實(shí)現(xiàn)了“優(yōu)先隊列”這種基礎(chǔ)數(shù)據(jù)類型。

我們將討論比較排序算法的理論基礎(chǔ)并在本章結(jié)尾總結(jié)若干排序算法和優(yōu)先隊列的應(yīng)用。

作為對排序算法領(lǐng)域的第一次探索，我們將學(xué)習(xí)兩種初級的排序算法以及其中一種的一個變體。深入學(xué)習(xí)這些相對簡單的算法的原因在于：第一，我們將通過它們熟悉一些術(shù)語和簡單的技巧；第二，這些簡單的算法在某些情況下比我們之后將會討論的復(fù)雜算法更有效；第三，以后你會發(fā)現(xiàn)，它們有助于我們改進(jìn)復(fù)雜算法的效率。

我們關(guān)注的主要對象是重新排列數(shù)組元素的算法，其中每個元素都有一個主鍵。排序算法的目標(biāo)就是將所有元素的主鍵按照某種方式排列（通常是按照大小或是字母順序）。排序后索引較大的主鍵大于等于索引較小的主鍵。元素和主鍵的具體性質(zhì)在不同的應(yīng)用中千差萬別。在Java中，元素通常都是對象，對主鍵的抽象描述則是通過一種內(nèi)置的機(jī)制（請見2.1.1.4節(jié)中的Comparable接口）來完成的?！芭判蛩惴惸０妗敝械腅xample類展示了我們的習(xí)慣約定：我們會將排序代碼放在類的sort()方法中，該類還將包含輔助函數(shù)less()和exch()（可能還有其他輔助函數(shù)）以及一個示例用例main()。Example類還包含了一些早期調(diào)試使用的代碼：測試用例main()將標(biāo)準(zhǔn)輸入得到的字符串排序，并用私有方法show()打印字符數(shù)組的內(nèi)容。我們還會在本章中遇到各種用于比較不同算法并研究它們的性能的測試用例。為了區(qū)別不同的排序算法，我們?yōu)橄鄳?yīng)的類取了不同的名字，用例可以根據(jù)名字調(diào)用不同的實(shí)現(xiàn)，例如Insertion.sort()、Merge.sort()、Quick.sort()等。

大多數(shù)情況下，我們的排序代碼只會通過兩個方法操作數(shù)據(jù)：less()方法對元素進(jìn)行比較，

exch()方法將元素交換位置。exch()方法的實(shí)現(xiàn)很簡單，通過Comparable接口實(shí)現(xiàn)less()方

法也不困難。將數(shù)據(jù)操作限制在這兩個方法中使得代碼的可讀性和可移植性更好，更容易驗證代碼的正確性、分析性能以及排序算法之間的比較。在學(xué)習(xí)具體的排序算法實(shí)現(xiàn)之前，我們先討論幾個對于所有排序算法都很重要的問題。

這個類展示的是數(shù)組排序?qū)崿F(xiàn)的框架。對于我們學(xué)習(xí)的每種排序算法，我們都會為這樣一個類實(shí)現(xiàn)一個sort()方法并將Example改為算法的名稱。測試用例會將標(biāo)準(zhǔn)輸入得到的字符串排序，但是這段代碼使我們的排序方法適用于任意實(shí)現(xiàn)了Comparable接口的數(shù)據(jù)類型。