漫畫：什么是計(jì)數(shù)排序？

計(jì)數(shù)排序

計(jì)數(shù)排序（Counting Sort）是一種針對(duì)于特定范圍之間的整數(shù)進(jìn)行排序的算法。它通過統(tǒng)計(jì)給定數(shù)組中不同元素的數(shù)量（類似于哈希映射），然后對(duì)映射后的數(shù)組進(jìn)行排序輸出即可。

我們以數(shù)組 [1,4,1,2,5,2,4,1,8] 為例進(jìn)行說明。

第一步：建立一個(gè)初始化為 0 ，長(zhǎng)度為 9 (原始數(shù)組中的最大值 8 加 1) 的數(shù)組 count[] :

第二步：遍歷數(shù)組 ?[1,4,1,2,5,2,4,1,8] ，訪問第一個(gè)元素 1 ，然后將數(shù)組 count[] 中下標(biāo)為 1 的元素加 1，表示當(dāng)前 1 出現(xiàn)了一次，即 count[1] = 1 ;

第三步：訪問數(shù)組 ?[1,4,1,2,5,2,4,1,8] 的第二個(gè)元素 4 ，然后將數(shù)組 count[] 中下標(biāo)為 4 的元素加 1 ，表示當(dāng)前訪問的元素 4 當(dāng)前出現(xiàn)了 1 次，即 ?count[4] = 1 ;

第四步：訪問數(shù)組 [1,4,1,2,5,2,4,1,8] 的第三個(gè)元素 1 ，然后將數(shù)組 count[] 中下標(biāo)為 1 的元素加 1，即 count[1] = 2 ，表示當(dāng)前 1 出現(xiàn)了 2 次：

第五步：訪問數(shù)組 ?[1,4,1,2,5,2,4,1,8] 的第四個(gè)元素 2 ，然后將數(shù)組 count[] 中下標(biāo)為 2 的元素加 1，即 count[2] = 1 ，表示當(dāng)前 2 出現(xiàn)了 1 次：

第六步：訪問數(shù)組 [1,4,1,2,5,2,4,1,8] 的第五個(gè)元素 5 ，然后將數(shù)組 count[] 中下標(biāo)為 5 的元素加 1，即 count[5] = 1 ，表示當(dāng)前 5 出現(xiàn)了 1 次：

第七步：訪問數(shù)組 [1,4,1,2,5,2,4,1,8] 的第六個(gè)元素 2 ，然后將數(shù)組 count[] 中下標(biāo)為 2 的元素加 1，即 count[2] = 2 ，表示當(dāng)前 2 出現(xiàn)了 2 次：

第八步：訪問數(shù)組 [1,4,1,2,5,2,4,1,8] 的第七個(gè)元素 4 ，然后將數(shù)組 count[] 中下標(biāo)為 4 的元素加 1，即 count[4] = 2 ，表示當(dāng)前 4 出現(xiàn)了 2 次：

第九步：訪問數(shù)組 [1,4,1,2,5,2,4,1,8] 的第八個(gè)元素 1 ，然后將數(shù)組 count[] 中下標(biāo)為 1 的元素加 1，即 count[1] = 3 ，表示當(dāng)前 1 出現(xiàn)了 3 次：

第十步：訪問數(shù)組 [1,4,1,2,5,2,4,1,8] 的第九個(gè)元素 8 ，然后將數(shù)組 count[] 中下標(biāo)為 8 的元素加 1，即 count[8] = 1 ，表示當(dāng)前 8 出現(xiàn)了 1 次：

此時(shí)遍歷數(shù)組 [1,4,1,2,5,2,4,1,8] 結(jié)束，我們得到了一個(gè) count[] 數(shù)組，而只要得到了這個(gè)count[]?數(shù)組，我們的排序算法就相當(dāng)于結(jié)束了，接下來的就只是輸出了。

如果不考慮計(jì)數(shù)排序的穩(wěn)定性，我們按照數(shù)組 count[] 中對(duì)應(yīng)下標(biāo)的出現(xiàn)次數(shù)直接輸出即可：

for(int?i?=?0;?i?????if?(count[i]?!=?0){
????????for(int?j?=?0;?j?????????????System.out.print(i?+?"?");
????????}
????}
}

為了保證計(jì)數(shù)排序的穩(wěn)定性，我們又該如何做呢？

先不考慮這么復(fù)雜，但是從宏觀的角度來看，我們的目的就是找到待排序數(shù)組中每一個(gè)元素在排序后數(shù)組當(dāng)中的正確位置。

首先看一下 count[] 數(shù)組本身， 數(shù)組中的 0 對(duì)于我們的輸出沒有任何影響，所以我們可以考慮將其直接去掉：

那么此時(shí)的我們就可根據(jù)去掉之后的數(shù)組得到排序后數(shù)組的一個(gè)輪廓圖：

但是這樣我們并不知道相同的數(shù)字在對(duì)應(yīng)原始數(shù)組 arr[] 中的哪一個(gè)元素，就相當(dāng)于直接輸出，而沒有考慮元素的相對(duì)順序；但是對(duì)這個(gè)過程的理解有助于我們接下來理解穩(wěn)定性的處理過程。

我們看到，數(shù)組 count[] 中的每一個(gè)值表示它所對(duì)應(yīng)的下標(biāo)在排序后數(shù)組的出現(xiàn)次數(shù)，那么我們遍歷數(shù)組（下標(biāo)從 1 開始），并對(duì)數(shù)組 count[] 中的每一個(gè)元素執(zhí)行 count[i] = count[i] + count[i-1]?會(huì)得到什么呢？

此時(shí)得到新的 count[] 將表示他們的位置信息，比如 3 表示它的下標(biāo) 1 一定出現(xiàn)在前 3 的位置；而緊接其后 5 則表示下標(biāo) 2 出現(xiàn)在第 4 和第 5 個(gè)位置；下標(biāo)為 3 的 count[3] = 5 ，其與前面的 count[2] 值相同，兩者之差也就表示其出現(xiàn)次數(shù)，0 次，所以不占位置；下標(biāo)為 4 的位置值為 7 ，則表示下標(biāo) 4 出現(xiàn)在第 6 和 7 的位置，依次類推，你也可以對(duì)新的 count[] 數(shù)組中的每一個(gè)元素做出解釋。

但我們?cè)趺纯赡芡Ａ粼谶@里呢？

有了這個(gè)新的 count[] 數(shù)組，我們?nèi)绾蔚玫皆財(cái)?shù)組 arr[] 在排序后的輸出數(shù)組 output[] ?中的正確位置呢？

回答了這個(gè)問題，穩(wěn)定的計(jì)數(shù)排序也就徹底理解了~~

第一步：從后向前遍歷，具體為什么是從后向前，看完了你就會(huì)明白了！首先是 i = n-1 = 8 ，然后計(jì)算出 arr[i] = arr[8] = 8 ?在排序后數(shù)組的正確位置 count[arr[i]] - 1 = count[8] - 1 = 8 ?，即排序后 arr[8] 的正確位置為 8 ，然后將 arr[8] 賦值給 output[8] = 8，但是 count[arr[8]] = count[8] 減 1 ：

第二步：i = n - 2 = 7 ，然后計(jì)算 arr[7] = 1 在排序后數(shù)組的正確位置 count[arr[7]] - 1 = count[1] - 1 = 2 ，即最后一個(gè) 1 在排序后的正確位置下標(biāo)為 2 ，然后將 count[arr[7]] 的值減 1 。這里為什么要減 1 ，因?yàn)槲覀円呀?jīng)找到了最后一個(gè) 1 ?的正確位置，目前就剩余兩個(gè) 1 沒有找到正確位置。

以此類推，就可以得到原數(shù)組 arr[] 中每一個(gè)元素在排序后的正確位置

這就是穩(wěn)定的計(jì)數(shù)排序，那我們?cè)賮砘卮鹨幌聻槭裁磸暮笙蚯氨闅v新的 count[] 數(shù)組？

因?yàn)橹挥羞@樣才能保證計(jì)數(shù)排序的穩(wěn)定性！比如原始數(shù)組 arr[] 中 3 個(gè) 1 的在排序后的相對(duì)位置就沒有發(fā)生變化，依舊保持：

實(shí)現(xiàn)代碼

public?class?CountingSort?{
????public?void?countingSort(int?arr[])?{
????????int?n?=?arr.length;
????????int?output[]?=?new?int[n];
??
????????int?count[]?=?new?int[256];
????????for(int?i?=?0;?i?256;?i++)?{
????????????count[i]?=?0;
????????}
??
????????for(int?i?=?0;?i?????????????++count[arr[i]];
????????}
??
????????for(int?i?=?1;?i?<=?255;?i++)?{
????????????count[i]?+=?count[i-1];
????????}
??
????????for(int?i?=?n-1;?i?>=?0;?i--)?{
????????????output[count[arr[i]]?-?1]?=?arr[i];
????????????--count[arr[i]];???
????????}
??
????????for(int?i?=?0;?i?????????????arr[i]?=?output[i];
????????}
????}
?
????public?static?void?main(String?args[])?{
????????CountingSort?os?=?new?CountingSort();
????????int?arr[]?=?{1,4,1,2,5,2,4,1,8};
??
????????os.countingSort(arr);

????????for(int?i?=?0;?i?????????????System.out.print(arr[i]?+?",");
??????  }
?????}
}

可是問題又來了，如果我們的數(shù)組變成了 arr[] = {-1,4,1,-2,5,-2,4,-1,8} ，上面介紹的計(jì)數(shù)排序的實(shí)現(xiàn)方式不就出現(xiàn)了問題嗎？因?yàn)閿?shù)組下標(biāo)也沒有負(fù)數(shù)的情況呀！

我們只需要找到數(shù)組 arr[] = {-1,4,1,-2,5,-2,4,-1,8} ?中的最小值 min = -2 ，以及最大值 max = 8 ，然后開辟一個(gè)大小為 max - min + 1 的 count[] 數(shù)組，統(tǒng)計(jì)出數(shù)組當(dāng)中每一個(gè)元素出現(xiàn)的次數(shù)即可，就像下面這樣：

其中數(shù)組 arr[] 的最小值 min = -2 ，-2 被映射到了 count[] 數(shù)組下標(biāo)為 0 的位置，原數(shù)組中包含 2 個(gè) -2 ，所以 count[0] = 2 ；原數(shù)組 arr[] 當(dāng)中有 3 個(gè) -1 ，其中 -1 - (-2) = 1 ，也就說 -1 映射到了 count[] 數(shù)組下表為 1 的位置，所以 count[1] = 3 .

得到了 count[] 數(shù)組，之后的操作還不簡(jiǎn)單嗎？記得自己調(diào)試一下奧！！！

改進(jìn)的計(jì)數(shù)排序?qū)崿F(xiàn)：

import?java.util.*;?

class?CountingSort??
{?
??
????static?void?countSort(int[]?arr)??
????{?
????????int?max?=?Arrays.stream(arr).max().getAsInt();?
????????int?min?=?Arrays.stream(arr).min().getAsInt();?
????????int?range?=?max?-?min?+?1;?
????????int?count[]?=?new?int[range];?
????????int?output[]?=?new?int[arr.length];?
????????for?(int?i?=?0;?i?????????{?
????????????count[arr[i]?-?min]++;?
????????}?
??
????????for?(int?i?=?1;?i?????????{?
????????????count[i]?+=?count[i?-?1];?
????????}?
??
????????for?(int?i?=?arr.length?-?1;?i?>=?0;?i--)??
????????{?
????????????output[count[arr[i]?-?min]?-?1]?=?arr[i];?
????????????count[arr[i]?-?min]--;?
????????}?
??
????????for?(int?i?=?0;?i?????????{?
????????????arr[i]?=?output[i];?
????????}?
????}?
??
????static?void?printArray(int[]?arr)??
????{?
????????for?(int?i?=?0;?i?????????{?
????????????System.out.print(arr[i]?+?"?");?
????????}?
????????System.out.println("");?
????}?
???
????public?static?void?main(String[]?args)?
????{?
????????int[]?arr?=?{-1,4,1,-2,5,-2,4,-1,8};?
????????countSort(arr);?
????????printArray(arr);?
????}?
}??

復(fù)雜度分析

時(shí)間復(fù)雜度

在整個(gè)代碼實(shí)現(xiàn)過程中，我們僅僅出現(xiàn)了一層的 for 循環(huán)，沒有出現(xiàn)任何 for 循環(huán)的嵌套，所以計(jì)數(shù)排序的時(shí)間復(fù)雜度為 量級(jí)。

空間復(fù)雜度

由于計(jì)數(shù)排序過程中，我們使用到了一個(gè) max - min + 1 大小的 count[] 數(shù)組，所以計(jì)數(shù)排序的空間復(fù)雜度為 量級(jí)。

優(yōu)缺點(diǎn)分析

1. 如果輸入數(shù)據(jù)的范圍 ?range = max - min + 1 ?不明顯大于要待排序數(shù)組的長(zhǎng)度 n = arr.length，則計(jì)數(shù)排序是相當(dāng)高效的，比時(shí)間復(fù)雜度為 的快速和歸并排序都優(yōu)秀。
2. 計(jì)數(shù)排序不是基于比較的排序算法，時(shí)間復(fù)雜度為 ? ，空間復(fù)雜度與數(shù)據(jù)范圍成正比。
3. 計(jì)數(shù)排序通常用作另一個(gè)排序算法（例如基數(shù)排序）的子過程。
4. 計(jì)數(shù)排序可以使用部分哈希（partial Hashing）在 的時(shí)間內(nèi)統(tǒng)計(jì)數(shù)據(jù)的頻率。
5. 計(jì)數(shù)排序適用于負(fù)輸入。
6. 計(jì)數(shù)排序不適用于小數(shù)的情況。