下面介紹的排序都為：非比較排序法
這里個(gè)人認(rèn)為在某些特定的地方非比較排序的速度非常明顯；
比如 ： 對(duì)待排數(shù)據(jù)中有順序分類，使用鴿巢總體分類，然后對(duì)不同類別的待排小數(shù)據(jù)集合采用 插入，快排等排序方式
Counting sort ：計(jì)數(shù)排序
描述：迭代待排序數(shù)組出元素x，確定小于此元素[z]個(gè)數(shù)，然后把x放到它在的最終輸出數(shù)組[z]上。
特性：與待排值有關(guān)；穩(wěn)定的排序算法；待排序數(shù)據(jù)要求過(guò)于嚴(yán)格，無(wú)實(shí)際用處；
算法的步驟如下：
1. 找出待排序的數(shù)組中最大和最小的元素
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
3. 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）
4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
Radix sort：基數(shù)排序
描述：將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的數(shù)前面補(bǔ)零. 然后, 從最低位開(kāi)始, 依次進(jìn)行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列.
排序方式：LSD 由右向左排；MSD 由左向右排
特性：非比較排序；待排數(shù)據(jù)需要統(tǒng)一格式；
假設(shè)需排序數(shù)列的取值范圍從1...k,我們于是建一個(gè)K+1元的數(shù)組 a[]，并賦初值為0，然后便開(kāi)始排序工作：
算法的步驟如下：
1. 按輸入順序讀入數(shù)列，如果所讀的元素為i(1<=i<=k),我們就將a[i]的值加一，這樣直到讀完所有的元素。
2. 讀出元素并排序：我們遍歷整個(gè)數(shù)組，如果a[i]=j(j>=0),我們就輸出j次i(表示元素i在原先數(shù)列中出現(xiàn)了j次),這樣輸出的序列就是已排序的。
3. 由于一般排序算法涉及到元素之間的比較，如果化成比較樹(shù)可以知道，這樣的排序算法復(fù)雜度的下限是O(N*lnN),而計(jì)數(shù)排序沒(méi)有比較元素，所以所需排序時(shí)間就少了，我們可以看到計(jì)數(shù)排序的復(fù)雜度為O(n*k)，其中k（k的定義同上）為合并排列所需的時(shí)間，是個(gè)常數(shù)。
4. 此算法適合所需排列的元素取值范圍不大的情況下，否則會(huì)造成空間的消耗，比如，一共100個(gè)元素，其取值范圍從1-100000，顯然這個(gè)時(shí)候用基數(shù)排序是不合適的。
Bucket sort：桶排序
描述：工作的原理是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序）。
桶排序以下列程序進(jìn)行：
1. 設(shè)置一個(gè)定量的陣列當(dāng)作空桶子。
2. 尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
3. 對(duì)每個(gè)不是空的桶子進(jìn)行排序。
4. 從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。
Pigeonhole sort：鴿巢排序
描述：是一種時(shí)間復(fù)雜度為O(n)且在不可避免遍歷每一個(gè)元素并且排序的情況下效率最好的一種排序算法. 但它只有在差值(或者可被映射在差值)很小的范圍內(nèi)的數(shù)值排序的情況下實(shí)用.
算法的步驟如下：與桶排同
整理 www.aygfsteel.com/Good-Game