上一回，在前面已經對冒泡排序、直接插入排序、希爾排序、選擇排序、快速排序、歸併排序、堆排序做了說明分析（具體詳情可點擊下方的鏈接查看）。本回，將對計數排序進行相關說明分析。
往期鏈接列表：
排序算法系列目錄說明
冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
希爾排序（Shell Sort）
選擇排序（Selection Sort）
快速排序（Quick Sort）
歸併排序（Merge Sort）
堆排序（Heap Sort）
計數排序（Counting Sort）
桶排序（Bucket Sort）
基數排序（Radix Sort）
計數排序（Counting Sort）
計數排序（Counting sort）是一種穩定的線性時間排序算法。
1. 基本思想
計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。
計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。
用來計數的數組C的長度取決於待排序數組中數據的範圍（等於待排序數組的最大值與最小值的差加上1），然後進行分配、收集處理：
分配。掃描一遍原始數組，以當前值-minValue作為下標，將該下標的計數器增1。
收集。掃描一遍計數器數組，按順序把值收集起來。
2. 實現邏輯
找出待排序的數組中最大和最小的元素
統計數組中每個值為i的元素出現的次數，存入數組C的第i項
對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）
反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1
3. 動圖演示
計數排序演示
舉個例子，假設有無序數列nums=[2, 1, 3, 1, 5], 首先掃描一遍獲取最小值和最大值，maxValue=5, minValue=1，於是開一個長度為5的計數器數組counter
(1) 分配。
統計每個元素出現的頻率，得到counter=[2, 1, 1, 0, 1]，例如counter[0]表示值0+minValue=1出現了2次。
(2) 收集。
counter[0]=2表示1出現了兩次，那就向原始數組寫入兩個1，counter[1]=1表示2出現了1次，那就向原始數組寫入一個2，依次類推，最終原始數組變為[1,1,2,3,5]，排序好了。
4. 複雜度分析
平均時間複雜度：O(n + k)
最佳時間複雜度：O(n + k)
最差時間複雜度：O(n + k)
空間複雜度：O(n + k)
當輸入的元素是n 個0到k之間的整數時，它的運行時間是 O(n + k)。。在實際工作中，當k=O(n)時，我們一般會採用計數排序，這時的運行時間為O(n)。
計數排序需要兩個額外的數組用來對元素進行計數和保存排序的輸出結果，所以空間複雜度為O(k+n)。
計數排序的一個重要性質是它是穩定的：具有相同值的元素在輸出數組中的相對次序與它們在輸入數組中的相對次序是相同的。也就是說，對兩個相同的數來說，在輸入數組中先出現的數，在輸出數組中也位於前面。
計數排序的穩定性很重要的一個原因是：計數排序經常會被用於基數排序算法的一個子過程。我們將在後面文章中介紹，為了使基數排序能夠正確運行，計數排序必須是穩定的。
5. 代碼實現
C版本：
計數排序（C）
Java版本：
計數排序（Java）
6. 優化改進
6.1 場景分析：
舉個極端的例子：如果排序的數組有200W個元素，但是這200W個數的值都在1000000-1000100，也就說有100個數，總共重複了200W次，現在要排序，怎麼辦？
這種情況排序，計數排序應該是首選。但是這時候n的值為200W，如果按原來的算法，k的值10001000，但是此時c中真正用到的地方只有100個，這樣對空間造成了極大的浪費。
6.2 改進思路：
針對c數組的大小，優化計數排序
6.3 改進代碼：
計數排序改進（Java）
總結
計數算法只能使用在已知序列中的元素在0-k之間，且要求排序的複雜度在線性效率上。
計數排序和基數排序很類似，都是非比較型排序算法。但是，它們的核心思想是不同的，基數排序主要是按照進制位對整數進行依次排序，而計數排序主要側重於對有限範圍內對象的統計。基數排序可以採用計數排序來實現。
源碼地址：https://github.com/7-sevens/algorithm
下一篇預告：桶排序（Bucket Sort）。欲知詳情，且聽下回分解。
微信公眾號
更多精品技術乾貨，歡迎關注微信公眾號：開發者小黑屋