概念：
計(jì)數(shù)排序不是一個(gè)比較排序算法，該算法于1954年由 Harold H. Seward提出，通過計(jì)數(shù)將時(shí)間復(fù)雜度降到了O(N)，利用數(shù)組下標(biāo)來缺的元素的正確位置
案例：
假設(shè)數(shù)組中有10個(gè)隨機(jī)數(shù),取值范圍0～10，要求用最快的速度把這20個(gè)證書從小到大進(jìn)行排序
考慮到這些整數(shù)只能夠在 0、1、2、3、4、5、6、7、8、9、10 這11個(gè)數(shù)中取值，取值范圍有限。所以，可以根據(jù)這有限的范圍，建立一個(gè)長(zhǎng)度為11的數(shù)組，數(shù)組下標(biāo)從0-10，元素初始值全為0
假設(shè)10個(gè)隨機(jī)數(shù)整數(shù)值如下
9，3，5，4，9，1，2，7，8，1
第一次計(jì)數(shù)
第二次計(jì)數(shù)
第三次計(jì)數(shù)
第四次計(jì)數(shù)
第五次計(jì)數(shù)
第六次計(jì)數(shù)
第七次計(jì)數(shù)
第八次計(jì)數(shù)
第九次計(jì)數(shù)
第十次計(jì)數(shù)
最終，當(dāng)數(shù)列遍歷完畢時(shí)，數(shù)組狀態(tài)如下
該數(shù)組中每一個(gè)下標(biāo)位置的值代表數(shù)列中對(duì)應(yīng)整數(shù)出現(xiàn)的次數(shù)。
有了這個(gè)統(tǒng)計(jì)結(jié)果，排序就簡(jiǎn)單多了，直接便利數(shù)組，輸出數(shù)組元素的下標(biāo)值，元素的值時(shí)幾，就輸出幾次
1，1，2，3，4，5，7，8，9，9
顯然，現(xiàn)在輸出的數(shù)列已經(jīng)是有序的了。
這就是計(jì)數(shù)排序的基本過程，它適用于一定范圍內(nèi)的整數(shù)排序。在取值范圍不是很大的情況下，它的性能甚至快過那些時(shí)間復(fù)雜度為 O(nlogn) 的排序。
代碼實(shí)現(xiàn)：
public class test {
public static void main(String[] args) {
int[] array = new int[] {4,4,6,5,3,2,8,1,7,10};
int[] sortedArray = countSort(array);
System.out.println(Arrays.toString(sortedArray));
}
public static int[] countSort(int[] array){
//1. 得到數(shù)列最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] > max){
max = array[i];
}
}
//2. 根據(jù)數(shù)列最大值確定統(tǒng)計(jì)數(shù)組的長(zhǎng)度
int[] countArray = new int[max+1];
for(int i=0; i<array.length; i++){
countArray[array[i]]++;
}
//遍歷統(tǒng)計(jì)數(shù)組，輸出結(jié)果
int index = 0;
int[] sortedArray = new int[array.length];
for(int i=0; i<countArray.length; i++){
for(int j=0; j<countArray[i]; j++){
sortedArray[index++] = i;
}
}
return sortedArray;
}
}
[1, 2, 3, 4, 4, 5, 6, 7, 8, 10]
這段代碼在開頭有一個(gè)步驟，就是求數(shù)列的最大整數(shù)值max。后面創(chuàng)建 的統(tǒng)計(jì)數(shù)組countArray，長(zhǎng)度是max+1，以此來保證數(shù)組的最后一個(gè)下 標(biāo)是max。
計(jì)數(shù)排序優(yōu)缺點(diǎn)
- 當(dāng)數(shù)列最大和最小值差距過大時(shí)，并不適合用計(jì)數(shù)排序
例如給出20個(gè)隨機(jī)整數(shù)，范圍在0到1億之間，這時(shí)如果使用計(jì)數(shù)排序，需要?jiǎng)?chuàng)建長(zhǎng)度為1億的數(shù)組，不但浪費(fèi)空間，而且時(shí)間復(fù)雜度也會(huì)隨之升高
- 當(dāng)數(shù)列元素不是整數(shù)時(shí)，也不適合用計(jì)數(shù)排序
如果數(shù)列中的元素都是小數(shù)，如25.213，或0.00 000 001 這樣的數(shù)字，則無法創(chuàng)建對(duì)應(yīng)統(tǒng)計(jì)數(shù)組，這樣顯然無法進(jìn)行計(jì)數(shù)排序。
對(duì)于這些局限性，另一種線性時(shí)間排序算法做出彌補(bǔ)、這周排序算法叫做桶排序
個(gè)人博客地址：http://blog.yanxiaolong.cn ｜ <font color = "orange"> 『縱有疾風(fēng)起，人生不言棄』 </font>
