1. 非比較排序

插入排序、歸并排序、堆排序、快速排序這四種排序算法，他們的運(yùn)行時(shí)間上界不會(huì)超過(guò)O(nlgn)。這些算法都有一個(gè)有趣的性質(zhì)：在排序的最終結(jié)果中，各元素的次序依賴于它們之間的比較。我們把這類(lèi)排序算法稱為比較排序。

可以證明，基于比較的排序算法在最壞情況下的時(shí)間下界是Ω(nlgn)。堆排序和歸并排序的運(yùn)行時(shí)間上界為O(nlgn)，因此這兩種排序算法都是漸進(jìn)最優(yōu)的比較排序算法。

而非基于比較的排序，如計(jì)數(shù)排序，桶排序，和在此基礎(chǔ)上的基數(shù)排序，則可以突破O(NlogN)時(shí)間下限，達(dá)到線性時(shí)間復(fù)雜度$$O(n)$$。但要注意的是，非基于比較的排序算法的使用都是有條件限制的，例如元素的大小限制，相反，基于比較的排序則沒(méi)有這種限制(在一定范圍內(nèi))。但并非因?yàn)橛袟l件限制就會(huì)使非基于比較的排序算法變得無(wú)用，對(duì)于特定場(chǎng)合有著特殊的性質(zhì)數(shù)據(jù)，非基于比較的排序算法則能夠非常巧妙地解決。

基數(shù)排序：O(dn) (d次調(diào)用桶排序)，空間復(fù)雜度 O(k)

桶排序：O(n)時(shí)間復(fù)雜度，O(n)空間復(fù)雜度

計(jì)數(shù)排序：O(n)時(shí)間復(fù)雜度，O(k)空間復(fù)雜度，每一個(gè)元素都是整數(shù)，并且位于0到k - 1之間

2. 計(jì)數(shù)排序

計(jì)數(shù)排序假設(shè)n個(gè)輸入元素中的每一個(gè)都是在0到k區(qū)間內(nèi)的一個(gè)整數(shù)，其中k為某個(gè)整數(shù)。當(dāng)k=O(n)時(shí)，排序的運(yùn)行時(shí)間為Θ(n)。

計(jì)數(shù)排序的思想是，對(duì)每一個(gè)輸入元素，計(jì)算小于它的元素個(gè)數(shù)，如果有10個(gè)元素小于它，那么它就應(yīng)該放在11的位置上，如果有17個(gè)元素小于它，它就應(yīng)該放在18的位置上。當(dāng)有幾個(gè)元素相同時(shí)，這一方案要略做修改，因?yàn)椴荒馨阉鼈兎旁谕粋€(gè)輸出位置上。下圖展示了實(shí)際的運(yùn)行過(guò)程。

計(jì)數(shù)排序

構(gòu)造輔助數(shù)組C，C的長(zhǎng)度為k。第一次遍歷A后，得到[0,k)區(qū)間上每個(gè)數(shù)出現(xiàn)的次數(shù)，將這些次數(shù)寫(xiě)入C，得到圖(a)的結(jié)果。然后把C中每個(gè)元素變成前面所有元素的累加和，得到圖(b)的結(jié)果。接下來(lái)，再次從后向前遍歷數(shù)組A，根據(jù)取出的元素查找C中對(duì)應(yīng)下標(biāo)的值，再把這個(gè)值作為下標(biāo)找到B中的位置，即是該元素排序后的位置。例如，圖中A的最后一個(gè)元素是3，找到C[3]是7，再令B[7]=3即可，然后順便把C[3]減一，這是防止相同的數(shù)被放到同一個(gè)位置。

計(jì)數(shù)排序的時(shí)間代價(jià)可以這樣計(jì)算，第一次遍歷A并計(jì)算C所花時(shí)間是Θ(n)，C累加所花時(shí)間是Θ(k)，再次遍歷A并給B賦值所花時(shí)間是Θ(n)，因此，總時(shí)間為Θ(k + n)。在實(shí)際中，當(dāng)k=O(n)時(shí)，我們一般會(huì)采用計(jì)數(shù)排序，這時(shí)的運(yùn)行時(shí)間為Θ(n)。

3. 基數(shù)排序

對(duì)于一組數(shù)據(jù)，我們可以按照每一位對(duì)它們進(jìn)行排序。比如，考慮下面一組十進(jìn)制數(shù)
329
457
839
355

先按最后一位從小到大排序，得到
355
457
329
839

再按中間一位從小到大排序，得到
329
839
355
457

最后按第一位從小到大排序，得到
329
355
457
839

其中，對(duì)任何一位的排序算法必須是穩(wěn)定的，即相同數(shù)字不能改變它們的前后順序。

基數(shù)排序算法的運(yùn)行時(shí)間很容易計(jì)算，對(duì)于n個(gè)k進(jìn)制d位數(shù)，假如每一位的排序使用計(jì)數(shù)排序算法，則該位排序用時(shí)為Θ(n + k)，總共d位數(shù)，總排序用時(shí)就是Θ(d(n + k))。當(dāng)d為常數(shù)且k=O(n)時(shí)，總排序時(shí)間為Θ(n)。

4. 桶排序

桶排序假設(shè)輸入是由一個(gè)隨機(jī)過(guò)程產(chǎn)生，該過(guò)程將元素均勻、獨(dú)立地分布在[0,1)區(qū)間上。

我們將[0,1)區(qū)間劃分為n個(gè)相同大小的子區(qū)間，稱為桶。然后將輸入數(shù)據(jù)分別放到各個(gè)桶中。如果數(shù)據(jù)分布得很均勻，每個(gè)桶中的數(shù)據(jù)就不會(huì)太多，都會(huì)維持在常數(shù)量級(jí)。我們先對(duì)每個(gè)桶中的元素排序，然后把所有桶中的元素順序列出來(lái)即可。下圖為n=10的一個(gè)案例。

桶排序.png

創(chuàng)建一個(gè)長(zhǎng)度也為10的數(shù)組，將A中的元素按照大小找到B中合適的位置，插入鏈表。之后，分別對(duì)B中每個(gè)鏈表中的元素執(zhí)行插入排序。最后將B中的所有元素依次取出即可。

現(xiàn)在分析桶排序的時(shí)間代價(jià)。將A中元素放入B用時(shí)Θ(n)，B中每個(gè)鏈表執(zhí)行插入排序的用時(shí)，可以證明是O(2 - 1/n)，于是總用時(shí)就是Θ(n) + n * O(2 - 1/n) = Θ(n)。具體證明過(guò)程比較難理解，這里我想給出一個(gè)容易理解的解釋，雖然不一定對(duì)，但還是可以幫助理解為什么總用時(shí)是Θ(n)。n個(gè)數(shù)放入n個(gè)桶，平均下來(lái)每個(gè)桶只有一個(gè)數(shù)，在實(shí)際中，可能有的多有的少，但都不會(huì)差得太離譜。因此我們可以認(rèn)為每個(gè)桶中只有常數(shù)個(gè)數(shù)，那么對(duì)常數(shù)個(gè)數(shù)執(zhí)行插入排序所用的時(shí)間當(dāng)然也就是O(1)了。于是n個(gè)桶總用時(shí)就是O(n)，加上前面的Θ(n)，桶排序總用時(shí)就是Θ(n)了。