桶排序、計(jì)數(shù)排序、基數(shù)排序

一、線性排序算法介紹

1.線性排序算法包括桶排序、計(jì)數(shù)排序、基數(shù)排序。
2.線性排序算法的時(shí)間復(fù)雜度為O(n)。
3.此3種排序算法都不涉及元素之間的比較操作，是非基于比較的排序算法。
4.對(duì)排序數(shù)據(jù)的要求很苛刻，重點(diǎn)掌握此3種排序算法的適用場(chǎng)景。

二、桶排序（Bucket sort）

1.算法原理：
1）將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行快速排序。
2）桶內(nèi)排完序之后，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。
2.使用條件
1）要排序的數(shù)據(jù)需要很容易就能劃分成m個(gè)桶，并且桶與桶之間有著天然的大小順序。
2）數(shù)據(jù)在各個(gè)桶之間分布是均勻的。
3.適用場(chǎng)景
1）桶排序比較適合用在外部排序中。
2）外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤且數(shù)據(jù)量大，但內(nèi)存有限無(wú)法將整個(gè)數(shù)據(jù)全部加載到內(nèi)存中。
4.應(yīng)用案例
1）需求描述：
有10GB的訂單數(shù)據(jù)，需按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序
但內(nèi)存有限，僅幾百M(fèi)B
2）解決思路：
掃描一遍文件，看訂單金額所處數(shù)據(jù)范圍，比如1元-10萬(wàn)元，那么就分100個(gè)桶。
第一個(gè)桶存儲(chǔ)金額1-1000元之內(nèi)的訂單，第二個(gè)桶存1001-2000元之內(nèi)的訂單，依次類推。
每個(gè)桶對(duì)應(yīng)一個(gè)文件，并按照金額范圍的大小順序編號(hào)命名（00，01，02，…，99）。
將100個(gè)小文件依次放入內(nèi)存并用快排排序。
所有文件排好序后，只需按照文件編號(hào)從小到大依次讀取每個(gè)小文件并寫到大文件中即可。
3）注意點(diǎn)：若單個(gè)文件無(wú)法全部載入內(nèi)存，則針對(duì)該文件繼續(xù)按照前面的思路進(jìn)行處理即可。

三、計(jì)數(shù)排序（Counting sort）

1.算法原理
1）計(jì)數(shù)其實(shí)就是桶排序的一種特殊情況。
2）當(dāng)要排序的n個(gè)數(shù)據(jù)所處范圍并不大時(shí)，比如最大值為k，則分成k個(gè)桶
3）每個(gè)桶內(nèi)的數(shù)據(jù)值都是相同的，就省掉了桶內(nèi)排序的時(shí)間。
2.代碼實(shí)現(xiàn)（參見(jiàn)下一條留言）
案例分析：
假設(shè)只有8個(gè)考生分?jǐn)?shù)在0-5分之間，成績(jī)存于數(shù)組A[8] = [2，5，3，0，2，3，0，3]。
使用大小為6的數(shù)組C[6]表示桶，下標(biāo)對(duì)應(yīng)分?jǐn)?shù)，即0，1，2，3，4，5。
C[6]存儲(chǔ)的是考生人數(shù)，只需遍歷一邊考生分?jǐn)?shù)，就可以得到C[6] = [2，0，2，3，0，1]。
對(duì)C[6]數(shù)組順序求和則C[6]=[2，2，4，7，7，8]，c[k]存儲(chǔ)的是小于等于分?jǐn)?shù)k的考生個(gè)數(shù)。
數(shù)組R[8] = [0，0，2，2，3，3，3，5]存儲(chǔ)考生名次。那么如何得到R[8]的呢？
從后到前依次掃描數(shù)組A，比如掃描到3時(shí)，可以從數(shù)組C中取出下標(biāo)為3的值7，也就是說(shuō)，到目前為止，包括自己在內(nèi)，分?jǐn)?shù)小于等于3的考生有7個(gè)，也就是說(shuō)3是數(shù)組R的第7個(gè)元素（也就是數(shù)組R中下標(biāo)為6的位置）。當(dāng)3放入數(shù)組R后，小于等于3的元素就剩下6個(gè)了，相應(yīng)的C[3]要減1變成6。
以此類推，當(dāng)掃描到第二個(gè)分?jǐn)?shù)為3的考生時(shí)，就會(huì)把它放入數(shù)組R中第6個(gè)元素的位置（也就是下標(biāo)為5的位置）。當(dāng)掃描完數(shù)組A后，數(shù)組R內(nèi)的數(shù)據(jù)就是按照分?jǐn)?shù)從小到大排列的了。
3.使用條件
1）只能用在數(shù)據(jù)范圍不大的場(chǎng)景中，若數(shù)據(jù)范圍k比要排序的數(shù)據(jù)n大很多，就不適合用計(jì)數(shù)排序；
2）計(jì)數(shù)排序只能給非負(fù)整數(shù)排序，其他類型需要在不改變相對(duì)大小情況下，轉(zhuǎn)換為非負(fù)整數(shù)；
3）比如如果考試成績(jī)精確到小數(shù)后一位，就需要將所有分?jǐn)?shù)乘以10，轉(zhuǎn)換為整數(shù)。

四、基數(shù)排序（Radix sort）

1.算法原理（以排序10萬(wàn)個(gè)手機(jī)號(hào)為例來(lái)說(shuō)明）
1）比較兩個(gè)手機(jī)號(hào)碼a，b的大小，如果在前面幾位中a已經(jīng)比b大了，那后面幾位就不用看了。
2）借助穩(wěn)定排序算法的思想，可以先按照最后一位來(lái)排序手機(jī)號(hào)碼，然后再按照倒數(shù)第二位來(lái)重新排序，以此類推，最后按照第一個(gè)位重新排序。
3）經(jīng)過(guò)11次排序后，手機(jī)號(hào)碼就變?yōu)橛行虻牧恕?br> 4）每次排序有序數(shù)據(jù)范圍較小，可以使用桶排序或計(jì)數(shù)排序來(lái)完成。
2.使用條件
1）要求數(shù)據(jù)可以分割獨(dú)立的“位”來(lái)比較；
2）位之間由遞進(jìn)關(guān)系，如果a數(shù)據(jù)的高位比b數(shù)據(jù)大，那么剩下的地位就不用比較了；
3）每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序，否則基數(shù)排序的時(shí)間復(fù)雜度無(wú)法做到O(n)。