## **計數排序** 計數排序不是基于比較的排序算法，其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。 ## **算法描述** 1. 找出待排序的數組中最大和最小的元素； 2. 統計數組中每個值為i的元素出現的次數，存入數組C的第i項； 3. 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）； 4. 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。 ## **穩定性** 最后給 b 數組賦值是倒著遍歷的，而且放進去一個就將C數組對應的值（表示前面有多少元素小于或等于A\[i\]）減去一。如果有相同的數x1,x2，那么相對位置后面那個元素x2放在（比如下標為4的位置），相對位置前面那個元素x1下次進循環就會被放在x2前面的位置3。從而保證了穩定性。 ## **適用場景** 排序目標要能夠映射到整數域，其最大值最小值應當容易辨別。例如高中生考試的總分數，顯然用0-750就OK啦；又比如一群人的年齡，用個0-150應該就可以了，再不濟就用0-200嘍。另外，計數排序需要占用大量空間，它比較適用于數據比較集中的情況。 ## **JAVA代碼實現** ``` public static void countSort(int[] a, int max, int min) { int[] b = new int[a.length];//存儲數組 int[] count = new int[max - min + 1];//計數數組 for (int num = min; num <= max; num++) { //初始化各元素值為0，數組下標從0開始因此減min count[num - min] = 0; } for (int i = 0; i < a.length; i++) { int num = a[i]; count[num - min]++;//每出現一個值，計數數組對應元素的值+1 } for (int num = min + 1; num <= max; num++) { //加總數組元素的值為計數數組對應元素及左邊所有元素的值的總和 count[num - min] += sum[num - min - 1] } for (int i = 0; i < a.length; i++) { int num = a[i];//源數組第i位的值 int index = count[num - min] - 1;//加總數組中對應元素的下標 b[index] = num;//將該值存入存儲數組對應下標中 count[num - min]--;//加總數組中，該值的總和減少1。 } //將存儲數組的值一一替換給源數組 for(int i=0;i<a.length;i++){ a[i] = b[i]; } } ```