從計數排序說起
計數排序是一種非基于元素比較的排序算法，而是將待排序數組元素轉化為計數數組的索引值，從而間接使待排序數組具有順序性。
計數排序的實現一般有兩種形式：基于輔助數組和基于桶排序。
基于輔助數組
整個過程包含三個數組：待排序數組A、計數數組B和輸出數組C。
簡單來說，就是通過統計待排序數組A中元素不同值的分布直方圖，生成計數數組B，然后計算計數數組B的前綴和(此步操作可以看成計算待排序數組A中每個元素的位置信息)，最后通過逆序循環將元素對應賦值到輸出數組C中，輸出數組C即是最終排序結果。
基于桶排序
其實就是用桶排序來維護穩定性，因為在每個桶中的元素是以隊列結構排序的，可以維護元素的順序。
主要步驟：
- 按元素的最大健值與最小健值之差來創建指定數量的桶，并在每個桶中創建一個隊列。
- 按順序遍歷待排序數組，將它們放到對應桶的隊列中。
- 按桶編號順序進行遍歷，將每個桶中隊列按順序輸出回原數組中。
計數排序的不足
可以看到輔助數組的長度和桶的數量由最大值和最小值決定，假如兩者之差很大，而待排序數組又很小，那么就會導致輔助數組或桶大量浪費。
基數排序
基數排序改善了計數排序，簡單來說，基數排序算法就是將整數或字符串切分成不同的數字或字符，然后按對應位置的數或字符分別進行比較，這樣就能將輔助數組或桶的數量降低到一個較小的值，經過多輪排序后得到最終的排序結果。
比如下面對于十進制的數值比較，只需要10個桶即可，但要保證每個桶能放得進所有元素。
第一階段：針對個位數將元素放到對應的桶中。
第二階段：針對十位數將元素放到對應的桶中。
第三階段：針對百位數將元素放到對應的桶中。
最終按照桶順序輸出得到排序結果。
桶排序
桶排序是改善計數排序的方法之一，其基本思想是將待排序數組分配到若干個桶內，然后每個桶內再各自進行排序，桶內的排序可以使用不同的算法，比如插入排序或快速排序，屬于分治法。每個桶執行完排序后，最后依次將每個桶內的有序序列拿出來，即得到完整的排序結果。
待排序數組的最大元素與最小元素分別為19和1，那么總的范圍區間可定義為[0,19]，假設用4個桶，則桶的區間分別為[0,4][5,9][10,14][15,19]。可以看到桶的數量可以控制在很小的范圍內，而且桶的容量大小可以動態擴充。
按照值將元素放到對應桶內。
按照桶順序將元素依次輸出得到排序結果。
總結
- 基數排序和桶排序可以看成是計數排序的泛化版本，使用了某些措施優化排序過程。
- 在桶排序中當桶的個數取最大值(max-min+1)的時候，就變成了計數排序，所以計數排序時桶排序的一種特例。
- 基數排序可以看做是多輪桶排序，基數排序以有效位的角度，每個有效位都進行一輪桶排序。
- 當用最大值作為基數時，基數排序就退化成了計數排序。
-------------推薦閱讀------------
我的開源項目匯總(機器&深度學習、NLP、網絡IO、AIML、mysql協議、chatbot)
為什么寫《Tomcat內核設計剖析》
2018匯總數據結構算法篇
2018匯總機器學習篇
2018匯總Java深度篇
2018匯總自然語言處理篇
2018匯總深度學習篇
2018匯總JDK源碼篇
2018匯總Java并發核心篇
2018匯總讀書篇
跟我交流，向我提問：
歡迎關注：
)
