前面說的那些排序算法，都是要通過比較來實(shí)現(xiàn)的晦毙。排序還能不通過比較來實(shí)現(xiàn)生巡？是的，計(jì)數(shù)排序就是這么神奇见妒。
一、排序思想
創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組甸陌，利用數(shù)組下標(biāo)來表示該元素须揣，用數(shù)組下標(biāo)對應(yīng)的值來表示元素出現(xiàn)的次數(shù)。然后遍歷計(jì)數(shù)數(shù)組即可钱豁。比如下標(biāo)為5耻卡，元素值為2，表示5出現(xiàn)兩次牲尺，連續(xù)寫兩次5即可卵酪。
歡迎大家關(guān)注我的公眾號 javawebkf，目前正在慢慢地將簡書文章搬到公眾號谤碳，以后簡書和公眾號文章將同步更新溃卡，且簡書上的付費(fèi)文章在公眾號上將免費(fèi)。
1. 案例：
假如待排序列arr如下：
5 7 4 8 3 5
最大元素是8蜒简，所以創(chuàng)建一個(gè)最大下標(biāo)為8的數(shù)組：
int[] count = new int[9];
遍歷待排序列瘸羡，第一個(gè)是5，所以count[5]++]搓茬，第二個(gè)是7犹赖，所以count[7]++……
最終count數(shù)組就是：
0 0 0 1 1 2 0 1 1 // 元素值
0 1 2 3 4 5 6 7 8 // 下標(biāo)
最后根據(jù)count數(shù)組，可以知道卷仑，3出現(xiàn)一次峻村，4出現(xiàn)一次，5出現(xiàn)兩次……就可以知道排序后應(yīng)該是這樣的：
3 4 5 5 7 8
這樣看似很完美锡凝，但是會存在兩個(gè)問題粘昨。
2. 問題一：
上面的5出現(xiàn)了兩次，最后排完序的的數(shù)組中下標(biāo)為2的那個(gè)5私爷，還是原序列中下標(biāo)為0的那個(gè)5嗎雾棺？也就是說，當(dāng)值相同的情況下衬浑，無法保證排序后相同元素出現(xiàn)的順序和排序前一致捌浩，這也就是我們說的不穩(wěn)定排序。如何優(yōu)化呢工秩？
我們給之前的數(shù)組中兩個(gè)5做上標(biāo)記尸饺，便于區(qū)分：
小紅 小白
5 7 4 8 3 5
- 然后和之前一樣进统，統(tǒng)計(jì)每個(gè)元素出現(xiàn)的次數(shù)，得到count數(shù)組：
0 0 0 1 1 2 0 1 1 // 元素值
0 1 2 3 4 5 6 7 8 // 下標(biāo)
- 接下來浪听，對count數(shù)組進(jìn)行變形螟碎，然后一個(gè)元素加上前一個(gè)元素，即：
count[i] = count[i] + count[i-1];
這樣一來迹栓，count數(shù)組就變成了：
0 0 0 1 2 4 4 5 6 // 元素值
0 1 2 3 4 5 6 7 8 // 下標(biāo)
- 然后掉分，創(chuàng)建一個(gè)新數(shù)組
resultArr，長度和原數(shù)組arr一樣克伊。從后往前遍歷原數(shù)組arr酥郭，第一個(gè)是5，標(biāo)記是小白愿吹，count[5]的值是4不从，表示小白排第四位，所以resultArr[4-1] = 5犁跪，同時(shí)count[5]--椿息，即把4變成3，下一個(gè)5就表示排第三位坷衍，小紅就排第三寝优，和原數(shù)組的順序一致。這樣一來惫叛，就將計(jì)數(shù)排序變成穩(wěn)定的了倡勇。
3. 問題二：
假如現(xiàn)有待排序列arr如下：
999 998 1000 995
按照之前的說法，count數(shù)組的最大下標(biāo)是arr數(shù)組最大值嘉涌，即如果要排這四個(gè)數(shù)妻熊，需要?jiǎng)?chuàng)建長度為1001的數(shù)組。而且仑最，下標(biāo)0到994的這些空間都用不到扔役，白白浪費(fèi)了。所以警医，count數(shù)組的長度應(yīng)該是max(arr) - min(arr) + 1亿胸，即用最大值減去最小值再加1即可。此案例中预皇，count的長度就是1000 - 995 + 1 = 6侈玄，那么每個(gè)元素應(yīng)該放在哪個(gè)下標(biāo)上呢？每個(gè)元素都減去最小元素吟温，得出來的值就對應(yīng)count的下標(biāo)序仙。比如999 - 995 = 4，那么999就應(yīng)該對應(yīng)count[4]鲁豪。
4. 計(jì)數(shù)排序的缺點(diǎn)：
從上面的分析可以知道潘悼，計(jì)數(shù)排序適合分布比較集中的數(shù)據(jù)律秃，即最大值和最小值相差不多，如果相差特別多治唤，就會很耗費(fèi)空間棒动。
二、代碼實(shí)現(xiàn)
public static void countSort(int[] arr) {
if (arr == null || arr.length == 1) {
return;
}
// 1. 找到數(shù)組中最大的數(shù)和最小的數(shù)
int max = arr[0];
int min = arr[0];
for (int i=1; i<arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
min = arr[i] < min ? arr[i] : min;
}
// 2. 定義count數(shù)組
int[] count = new int[max - min + 1];
// 3. 遍歷原數(shù)組宾添，進(jìn)行計(jì)數(shù)
for (int i=0; i<arr.length; i++) {
count[arr[i] - min]++;
}
// 4. 對count數(shù)組進(jìn)行變形船惨，讓計(jì)數(shù)排序變成穩(wěn)定的
for (int i=1; i<count.length; i++) {
count[i] += count[i-1];
}
// 5. 創(chuàng)建接收結(jié)果的數(shù)組
int[] result = new int[arr.length];
// 6. 倒序遍歷原數(shù)組，并且將結(jié)果存到result數(shù)組中
for (int i=arr.length-1; i>=0; i--) {
result[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min] --;
}
// 7. 把result數(shù)組拷貝回原數(shù)組即可
System.arraycopy(result, 0, arr, 0, arr.length);
}
