什麼是計數排序？
————— 第二天 —————
————————————
假定20個隨機整數的值如下：
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9
如何給這些無序的隨機整數排序呢？
非常簡單，讓我們遍歷這個無序的隨機數列，每一個整數按照其值對號入座，對應陣列下標的元素進行加1操作。
比如第一個整數是9，那麼陣列下標為9的元素加1：
第二個整數是3，那麼陣列下標為3的元素加1：
繼續遍歷數列並修改陣列......
最終，數列遍歷完畢時，陣列的狀態如下：
陣列每一個下標位置的值，代表了數列中對應整數出現的次數。
有了這個“統計結果”，排序就很簡單了。直接遍歷陣列，輸出陣列元素的下標值，元素的值是幾，就輸出幾次：
0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
顯然，這個輸出的數列已經是有序的了。
這段程式碼在一開頭補充了一個步驟，就是求得數列的最大整數值max。後面建立的統計陣列countArray，長度就是max+1，以此保證陣列的最後一個下標是max。
95 ，94，91，98，99，90，99，93，91，92
怎麼解決這個問題呢？
很簡單，我們不再以（輸入數列的最大值+1）作為統計陣列的長度，而是以（數列最大值和最小值的差+1）作為統計陣列的長度。
同時，數列的最小值作為一個偏移量，用於統計陣列的對號入座。
以剛才的數列為例，統計陣列的長度為 99-90+1 = 10 ，偏移量等於數列的最小值 90 。
對於第一個整數95，對應的統計陣列下標是 95-90 = 5，如圖所示：
什麼意思呢？讓我們看看下面的例子：
給定一個學生的成績表，要求按成績從低到高排序，如果成績相同，則遵循原表固有順序。
那麼，當我們填充統計陣列以後，我們只知道有兩個成績並列95分的小夥伴，卻不知道哪一個是小紅，哪一個是小綠：
下面的講解會有一些燒腦，請大家扶穩坐好。我們仍然以剛才的學生成績表為例，把之前的統計陣列變形成下面的樣子：
這是如何變形的呢？統計陣列從第二個元素開始，每一個元素都加上前面所有元素之和。
為什麼要相加呢？初次看到的小夥伴可能會覺得莫名其妙。
因為原來的統計陣列（未變形）裡面儲存的是各個元素的個數，那麼向後疊加的目的就是為了計算元素排序後的最終位置（準確來說是 最大的最終位置 ）。比如元素 90 的個數為1, 94個數也為 1，那麼向後疊加後94對應的統計陣列（變形後）為 2 ，那它就最終的位置就是第二。
變形後的統計陣列（countArray）中的值就代表著原數列元素排序後 最大的最終位置 （在重複元素的情況下還會有其他相同元素在此位置之前） 。比如下標是5的值為4，說明 95 排序後的位置最大就是第四。
通過變形後的統計陣列中的值對應排序後陣列sortedArray的下標來控制最終的位置( 4 <---> sortedArray[ 4 -1] );
那麼另外一個95在哪？我們可以將accountArray[5] 裡面的值減一（4-1），讓它排在第三位。
通過這樣的遞減，就可以將重複的元素全部安排妥當，先遇到小綠，就先安排小綠，再遇到小紅，然後安排小紅，這樣小綠和小紅排序前和排序後的次序也就可以相同了。
下來我們具體分析整個過程：
我們建立輸出陣列sortedArray，長度和輸入數列一致。然後從後向前遍歷輸入數列：
第一步，我們遍歷成績表最後一行的小綠：
小綠是95分，我們找到countArray下標是5的元素，值是4，代表小綠的成績排名位置在第4位。
同時，我們給countArray下標是5的元素值減1，從4變成3,，代表著下次再遇到95分的成績時，最終排名是第3。
第二步，我們遍歷成績表倒數第二行的小白：
小白是94分，我們找到countArray下標是4的元素，值是2，代表小白的成績排名位置在第2位。
同時，我們給countArray下標是4的元素值減1，從2變成1,，代表著下次再遇到94分的成績時 （實際上已經遇不到了） ，最終排名是第1。
第三步，我們遍歷成績表倒數第三行的小紅：
小紅是95分，我們找到countArray下標是5的元素，值是3（最初是4，減1變成了3），代表小紅的成績排名位置在第3位。
同時，我們給countArray下標是5的元素值減1，從3變成2,，代表著下次再遇到95分的成績時（實際上已經遇不到了），最終排名是第2。
這樣一來，同樣是95分的小紅和小綠就能夠清楚地排出順序了，也正因此，優化版本的計數排序屬於 穩定排序 。
後面的遍歷過程以此類推，這裡就不再詳細描述了。
1.當數列最大最小值差距過大時，並不適用計數排序。
比如給定20個隨機整數，範圍在0到1億之間，這時候如果使用計數排序，需要建立長度1億的陣列。不但嚴重浪費空間，而且時間複雜度也隨之升高。
2.當數列元素不是整數，並不適用計數排序。
如果數列中的元素都是小數，比如25.213，或是0.00000001這樣子，則無法建立對應的統計陣列。這樣顯然無法進行計數排序。
原文釋出時間為：2018-10-19
本文作者： 小灰
本文來自雲棲社群合作伙伴“ ofollow,noindex">趣談程式設計 ”，瞭解相關資訊可以關注“ 趣談程式設計 ”。