演算法從入門到「放棄」（5）- 計數排序
演算法從入門到「放棄」（5）- 計數排序
來自專欄 AnotherWorld
本系列文章
演算法從入門到「放棄」（1）- 什麼是演算法？
演算法從入門到「放棄」（2）- 分而治之和解決循環
排序系列
1. 演算法從入門到「放棄」（3）- 快速排序
2. 演算法從入門到「放棄」（4）- 插入排序
本文提煉
計數排序演算法，一種穩定的線性時間整數排序演算法。
什麼是計數排序？
定義來自於維基百科，計數排序，Counting Sort.
計數排序是一種穩定的線性時間整數排序演算法。計數排序使用一個額外的輔助數組/計數數組C，其中第i 個元素是待排序數組A 中值等於i 的元素的個數。然後根據數組C 來將A 中的元素排到正確的位置。
計數排序，以及它在基數排序(Radix Sort) 中的應用，都是由哈羅德·h·蘇厄德在1954年發明的。
基本思想
輸入：一系列的無序數字組成的輸入數組A，裡面有n 個元素，每個元素都是非負的整數，數組中元素值的範圍是0到k
經過：過程中，我們需要目標數組B[1...n] 用來儲存最終結果，計數數組C[0...k] 用來暫時儲存過程中數據。具體經過如下：
初始狀態下，待排序數組A 有n 個數，計數數組C 中根據A 中元素值的範圍0到k 定下有幾個數+1（+1 是為了給0一個位子）；然後根據數組A 中各個元素的個數確定計數數組中每個位置的個數。舉個栗子，比如A 中元素有2,5,3,0,2,3,0,3，元素值的範圍為0到5，那麼計數數組中就會只有5+1=6 個元素（0至5）；因為A 中0 有2個，所以C 中0 的位置是2，同理，可以知道整個計數數組C 中1的位置是0, 2的位置是2, 3的位置是3, 4的位置是0, 5的位置是1。
接著，在計數數組C 中，從1的位置開始（為什麼不是從0的位置開始？因為不存在C[-1]），C[i] = C[i] + C[i-1]。這個循環結束後，我們現在的計數數組變為2, 2, 4, 7, 7, 8.
最後一步，套用如下偽代碼：
for j = A.length downto 1 //從原來的數組的長度開始降到1為止 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1
代碼解釋起來比較複雜，我們直接看過程
j 一開始為A 的長度，8。第一行：A[j]=3，C[3]=7，B[7]=A[8]=3；第二行：C[3]=C[3]-1=7-1=6. 第一次迭代之後，B數組有了第一個數，B[7]=3，C數組變為了2, 2, 4, 6, 7, 8.
我們再迭代一次。j 現在降成了7。第一行：A[j]=A[7]=0，C[0]=2，B[2]=A[7]=0；第二行：C[0]=C[0]-1=2-1=1. 第二次迭代之後，B數組增加了第二個數，B[2]=0， C數組變為了1, 2, 4, 6, 7, 8.
迭代方法如上所示，一直持續到j 變為1.
輸出：如上面那個例子，最終結果就是B數組為0, 0, 2, 2, 3, 3, 3, 5.
圖解
這裡有一個University of San Francisco 電腦科學部門專門針對計數演算法創建的網頁，可以隨意輸入數組，大小，然後把排序的過程展示給我們。
評價演算法好壞
分類：排序演算法
數據結構：數組
(下面的n 是數組中元素的個數，k 是數組中最大的值)
最壞時間複雜度：O(n+k)
最優時間複雜度：O(n+k)
平均時間複雜度：O(n+k)；非常穩定
空間複雜度：O(n+k)；也有極端情況，當數組中最大值遠小於數組中元素的數量，空間這時候會被運用得很有效率，O(k).
實例分析
我們假設有一個輸入數組A, [3,4,2,1,0,0,4,3,4,2].
這裡的元素共10個，n為10；最大值k 為4.
輸入數組如下圖：
具體過程參考基本思想中的經過部分。大家可以先推一遍，不懂的可以先參考這個網站（網站有一個漏洞，顯示k 為5，我們理解為4即可；但不影響理解，因為在後面的步驟中是對的，計數數組C 範圍還是從0到4）。不明白的部分歡迎在留言區貼上，我看到都會回復哦。
也歡迎大家把你的想法和過程分享在留言區哦。
流程展示圖
圖片來源：Efficient Algorithms
代碼展示
偽代碼
在下一篇文章中，將著重講的是冒泡排序演算法。
如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！
推薦閱讀：
