上一篇： 桶排序
下一篇： 基數排序
計數排序（counting sort）就是一種犧牲記憶體空間來換取低時間複雜度的排序算法，是桶排序的一種擴充
核心思想：
對于一個輸入數組中的任意一個元素x， 知道了這個數組中比x小的元素的個數，那麼我們就可以直接把x放到（x+1）的位置上。這就是計數排序的基本思想。
比如說有5個元素小于x，那就把x放到第六個位置上。當有元素相等時，需要略作修改，因為不能把他們都放在同一個位置上。
基于這個思想，計數排序的一個主要問題就是如何統計數組中元素的個數。再加上輸入數組中的元素都是0-k區間的一個整數這個條件，那麼就可以通過另外一個數組的位址表示輸入元素的值，數組的值表示元素個數的方法來進行統計。
流程：
1：首先找到此組資料的最大值與最小值–max min, 初始化桶int []buckets=new int[max-min+1] --因為我們需要這些資料的值作為數組buckets的索引，是以定義max-min+1個桶
2：對資料進行對号入桶：我們周遊所有資料，将每個值為 arr[index]-min 的資料放入到第 arr[index]-min個桶中，比方說第一個的值為 5，則放入5-min(2)=buckets[3]的桶中
并記錄該桶放入資料的個數buckets[index-min]++;
3:周遊所有的桶，依次從桶中取出資料将其指派與arr數組，:每取出一次計數器減減；直到計數器為0為止 ；到此排序完成
//将對應的元素值作為數組的索引放入數組中并計數，然後按根據計數器的個數從數組中一次取出，即為有序排列，缺點不穩定,不能保證相同元素在排序後前後位置依然相同
public static int[] countingSort(int[] arr){
if (arr == null || arr.length == 0) {
return null;
}
int max= Arrays.stream(arr).max().getAsInt();
int min= Arrays.stream(arr).min().getAsInt();
int[] buckets = new int[max-min+1];
//找出每個數字出現的次數
for (int j : arr) {
buckets[j-min]++;
}
int arrIndex = 0;
for(int i = 0; i < buckets.length; i++){
while(buckets[i]> 0){
arr[arrIndex++] = i+min;
buckets[i]--;
}
}
return arr;
}
以上無法保證排序的穩定性，不能保證相同元素在排序後前後位置依然相同。
改進
放入桶中的方式依然相同，隻是後續對計數桶資料進行求和處理，即從從index=1位置開始，目前位置的元素=目前位置元素+其前一位置的元素；目的是記錄每個桶上的元素最後次出現的位置 求和後的數組countBucketArr 中的每一個元素的值value-1對應着arr數組中的元素最後次出現的位置，即需要指派給零時數組sortedArr的索引—代碼裡有詳細解釋
public static int[] countingSort1(int[] arr){
boolean isLegal=arr==null|| arr.length ==0;
if (isLegal) {
return arr;
}
int max= Arrays.stream(arr).max().getAsInt();
int min= Arrays.stream(arr).min().getAsInt();
int countBucket=max-min+1;//計數
int[] countBucketArr=new int[countBucket];//計數桶
int[] sortedArr=new int[arr.length];
for (int j : arr) {//記錄元素出現次數
//countBucketArr[max-j]++;//大到小
countBucketArr[j-min]++;
}
/* arr[6,1,2,7,9,6]--> buckets[j-min(1)]++ --> countBucketArr[1,1,0,0,0,2,1,0,1]①
* --> countBucketArr[i]+=countBucketArr[i-1] ②--->countBucketArr[1,2,2,2,2,4,5,5,6]③---->countBucketArr[arr[j]-min]-1]=arr[j]--> [1, 2, 6, 6, 7, 9]
*
* 解析：
* ③中的4元素對應着①中的2元素。而①中的2則映射着arr值=6的元素(如果倒叙周遊則先取最後位置的6) 是以我們給臨時數組指派的索引即為4-1=3的位置
* 推導：
* 比如arr中最後的6元素 在①中位于索引為5的位置且出現2次，經過②操作後在③中表示①中2的元素(即arr中的元素6)最終會出現在元素location=4減一的位置即新數組索引3的位置
* 而location=arr[5]-min=6-1=5-->countBucketArr[5]=4-->綜合下得到countBucketArr[arr[j]-min]-1]=arr[j]=6
*
試想如果在最終指派的時候正序周遊，則最開始擷取的就是arr中第一個元素6放在新數組sortedArr的索引3的位置，然後計數器從4減一為3，則
第arr中最後一個元素6則被放在sortedArr的索引2的位置，則新數組中第一6元素在第二個6元素後。就失去了算法的穩定性，是以必須倒序周遊才能保證算法的穩定性
* 注：減一因為數組索引為0開始索引指派的時候需要減一
* */
//計算數組中小于等于每個元素的個數,因為小于等于0的數的個數就是等于0的數的個數， 即從countBucketArr中的第一個元素開始，每一項和前一項相加
for (int i = 1; i < countBucketArr.length; ++i) {
countBucketArr[i]+=countBucketArr[i-1];
}
//填充數組
//保證最後一個等于數組countBucketArr下标j的元素排在最後，然後countBucketArr[i]–，倒數第二個等于下标i的元素排在這個元素之前
//記錄每個桶位上的最後個元素出現的位置
for(int j=arr.length-1;j>=0;j--){
//因為數組的下标從0開始是以小于等于arr[j]的數的個數為x就應該将該數放在數組sortedArr的第x-1個位置
sortedArr[countBucketArr[arr[j]-min]-1] = arr[j] ;
countBucketArr[arr[j]-min]--;
// sortedArr[countBucketArr[max-arr[j]]-1] = arr[j];//大到小
// countBucketArr[max-arr[j]]--;//大到小
}
arr=sortedArr.clone();
return arr;
}
擴充：對字元串如何使用計數排序
//計數排序字元串
public static String[] countingSortWithStr(String[] arr){
if (arr==null||arr.length==0){
return null ;
}
//元素最長位數
int maxLength =Arrays.stream(arr).max(Comparator.comparing(String::length)).get().length();
//排序結果數組
String[] sortedArr = new String[arr.length];
int[] buckets = new int[128];//最大ASCII 127 最小0 極值128
//從個位開始比較，一直比較到最高位
for(int k = maxLength;k >0;k--) {
for (String s : arr) {
int index = 0;
//w位數不足的位置補0
if (s.length() >= k ) {
index = s.charAt(k-1);
}
buckets[index]++;
}
//将各個桶中的數字個數，轉化成各個桶中最後一個數字的下标索引
for (int i = 1; i < buckets.length; i++) {
buckets[i]+=buckets[i-1];
}
//周遊原始數列，進行排序
for (String s : arr) {
int index = 0;
if (s.length() >= k) {
index = s.charAt(k - 1);
}
sortedArr[buckets[index] - 1] = s;
buckets[index]--;
}
Arrays.fill(buckets, 0);
}
return sortedArr;
}
同樣8000個數，計數排序非常快
計數排序是一個穩定的排序算法.
- 當輸入的元素是n個0到k之間的整數時,時間複雜度是O(n+k),空間複雜度也是O(n+k),其排序速度快于任何比較排序算法.
- 當k不是很大并且序列比較集中時,計數排序是一個很有效的排序算法.
- 計數排序的缺點是當最大值最小值差距過大時,不适用計數排序,當元素不是整數值,不适用計數排序.
- 可以看到輔助數組的長度和桶的數量由最大值和最小值決定，假如兩者之差很大，而待排序數組又很小，那麼就會導緻輔助數組或桶大量浪費。
穩定性:計數排序很重要的性質是它是穩定的。即使是相同的數，在輸入數組中先出現的數，在輸出數組中也位于前面。通常這種穩定性隻有當排序資料還附帶衛星資料是才很重要。其次，它也是基數排算法的一個子過程，因為基數排序必須要求子程式是穩定的。
一般使用在量非常大，數組元素之間範圍小的場景 比如：2 萬名員工的年齡(量大，範圍小(0-100歲))；50萬人查詢聯考成績（0-750分）