排序就是將一組對象按照某種邏輯順序重新排列的過程奕删。比如，信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時代早期孕暇，大家普遍認(rèn)為30%的計(jì)算周期都用在了排序上。如果今天這個比例降低了，可能的原因之一是如今的排序算法更加高效妖滔，而并非排序的重要性降低了∷硐現(xiàn)在計(jì)算機(jī)的廣泛使用使得數(shù)據(jù)無處不在，而整理數(shù)據(jù)的第一步通常就是進(jìn)行排序座舍。所有的計(jì)算機(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é)計(jì)算中有著重要的地位，它能夠應(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)先隊(duì)列”這種基礎(chǔ)數(shù)據(jù)類型揩徊。
我們將討論比較排序算法的理論基礎(chǔ)并在本章結(jié)尾總結(jié)若干排序算法和優(yōu)先隊(duì)列的應(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接口）來完成的“崖ǎ“排序算法類模版”中的Example類展示了我們的習(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ù)操作限制在這兩個方法中使得代碼的可讀性和可移植性更好翘瓮，更容易驗(yàn)證代碼的正確性贮折、分析性能以及排序算法之間的比較。在學(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ù)類型今穿。
