這是小川的第385次更新，第413篇原創
01 計數排序算法概念
計數排序不是一個比較排序算法，該算法于1954年由 Harold H. Seward提出，通過計數将時間複雜度降到了
O(N)
。
02 基礎版算法步驟
第一步：找出原數組中元素值最大的，記為
max
第二步：建立一個新數組
count
，其長度是
max
加1，其元素預設值都為0。
第三步：周遊原數組中的元素，以原數組中的元素作為
count
數組的索引，以原數組中的元素出現次數作為
count
數組的元素值。
第四步：建立結果數組
result
，起始索引
index
第五步：周遊
count
數組，找出其中元素值大于0的元素，将其對應的索引作為元素值填充到
result
數組中去，每處理一次，
count
中的該元素值減1，直到該元素值不大于0，依次處理
count
中剩下的元素。
第六步：傳回結果數組
result
03 基礎版代碼實作
public int[] countSort(int[] A) {
// 找出數組A中的最大值
int max = Integer.MIN_VALUE;
for (int num : A) {
max = Math.max(max, num);
}
// 初始化計數數組count
int[] count = new int[max+1];
// 對計數數組各元素指派
for (int num : A) {
count[num]++;
}
// 建立結果數組
int[] result = new int[A.length];
// 建立結果數組的起始索引
int index = 0;
// 周遊計數數組，将計數數組的索引填充到結果數組中
for (int i=0; i<count.length; i++) {
while (count[i]>0) {
result[index++] = i;
count[i]--;
}
}
// 傳回結果數組
return result;
}
04 優化版
基礎版能夠解決一般的情況，但是它有一個缺陷，那就是存在空間浪費的問題。
比如一組資料
{101,109,108,102,110,107,103}
，其中最大值為110，按照基礎版的思路，我們需要建立一個長度為111的計數數組，但是我們可以發現，它前面的
[0,100]
的空間完全浪費了，那怎樣優化呢？
将數組長度定為
max-min+1
，即不僅要找出最大值，還要找出最小值，根據兩者的差來确定計數數組的長度。
public int[] countSort2(int[] A) {
// 找出數組A中的最大值、最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : A) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 初始化計數數組count
// 長度為最大值減最小值加1
int[] count = new int[max-min+1];
// 對計數數組各元素指派
for (int num : A) {
// A中的元素要減去最小值，再作為新索引
count[num-min]++;
}
// 建立結果數組
int[] result = new int[A.length];
// 建立結果數組的起始索引
int index = 0;
// 周遊計數數組，将計數數組的索引填充到結果數組中
for (int i=0; i<count.length; i++) {
while (count[i]>0) {
// 再将減去的最小值補上
result[index++] = i+min;
count[i]--;
}
}
// 傳回結果數組
return result;
}
05 進階版步驟
以數組
A = {101,109,107,103,108,102,103,110,107,103}
為例。
第一步：找出數組中的最大值
max
、最小值
min
count
，其長度是max-min加1，其元素預設值都為0。
count
count
第四步：對
count
數組變形，新元素的值是前面元素累加之和的值，即
count[i+1] = count[i+1] + count[i];
第五步：建立結果數組
result
，長度和原始數組一樣。
第六步：周遊原始數組中的元素，目前元素A[j]減去最小值
min
，作為索引，在計數數組中找到對應的元素值
count[A[j]-min]
，再将count[A[j]-min]的值減去1，就是
A[j]
在結果數組
result
中的位置，做完上述這些操作，
count[A[j]-min]
自減1。
是不是對第四步和第六步有疑問？為什麼要這樣操作？
第四步操作，是讓計數數組
count
存儲的元素值，等于原始數組中相應整數的最終排序位置，即計算原始數組中的每個數字在結果數組中處于的位置。
比如索引值為9的
count[9]
，它的元素值為10，而索引9對應的原始數組
A
中的元素為9+101=110（要補上最小值
min
，才能還原），即110在排序後的位置是第10位，即result[9] = 110，排完後
count[9]
的值需要減1，
count[9]
變為9。
再比如索引值為6的
count[6]
，他的元素值為7，而索引6對應的原始數組
A
中的元素為6+101=107，即107在排序後的位置是第7位，即
result[6] = 107
，排完後
count[6]
count[6]
變為6。
如果索引值繼續為6，在經過上一次的排序後，
count[6]
的值變成了6，即107在排序後的位置是第6位，即
result[5] = 107
count[6]
count[6]
變為5。
至于第六步操作，就是為了找到A中的目前元素在結果數組
result
中排第幾位，也就達到了排序的目的。
06 進階版代碼實作
public int[] countSort3(int[] A) {
// 找出數組A中的最大值、最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : A) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 初始化計數數組count
// 長度為最大值減最小值加1
int[] count = new int[max-min+1];
// 對計數數組各元素指派
for (int num : A) {
// A中的元素要減去最小值，再作為新索引
count[num-min]++;
}
// 計數數組變形，新元素的值是前面元素累加之和的值
for (int i=1; i<count.length; i++) {
count[i] += count[i-1];
}
// 建立結果數組
int[] result = new int[A.length];
// 周遊A中的元素，填充到結果數組中去
for (int j=0; j<A.length; j++) {
result[count[A[j]-min]-1] = A[j];
count[A[j]-min]--;
}
return result;
}
07 進階版的延伸之一
如果我們想要原始數組中的相同元素按照本來的順序的排列，那該怎麼處理呢？
依舊以上一個數組
{101,109,107,103,108,102,103,110,107,103}
為例，其中有兩個107，我們要實作第二個107在排序後依舊排在第一個107的後面，可以在第六步的時候，做下變動就可以實作，用倒序的方式周遊原始數組，即從後往前周遊
A
數組。
從後往前周遊，第一次遇到107（
A[8]
）時，107-101 = 6，
count[6] = 7
，即第二個107要排在第7位，即
result[6] = 107
，排序後
count[6] = 6
繼續往前，第二次遇到107（
A[2]
count[6] = 6
，即第一個107要排在第6位，即
result[5] = 107
count[6] = 5
public int[] countSort4(int[] A) {
// 找出數組A中的最大值、最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : A) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 初始化計數數組count
// 長度為最大值減最小值加1
int[] count = new int[max-min+1];
// 對計數數組各元素指派
for (int num : A) {
// A中的元素要減去最小值，再作為新索引
count[num-min]++;
}
// 計數數組變形，新元素的值是前面元素累加之和的值
for (int i=1; i<count.length; i++) {
count[i] += count[i-1];
}
// 建立結果數組
int[] result = new int[A.length];
// 周遊A中的元素，填充到結果數組中去，從後往前周遊
for (int j=A.length-1; j>=0; j--) {
result[count[A[j]-min]-1] = A[j];
count[A[j]-min]--;
}
return result;
}
08 進階版的延伸之二
既然從後往前周遊原始數組的元素可以保證其原始排序，那麼從前往後可不可以達到相同的效果？
答案時可以的。
max
min
count
max-min加1再加1
，其元素預設值都為0。
count
count
count
count[i+1] = count[i+1] + count[i];
result
第六步：從前往後周遊原始數組中的元素，目前元素
A[j]
減去最小值
min
count[A[j]-min]
，就是
A[j]
result
count[A[j]-min]
自增加1。
{101,109,107,103,108,102,103,110,107,103}
為例，其中有兩個107，我們要實作第一個107在排序後依舊排在第二個107的前面。
此時計數數組
count
為
{0, 1, 2, 5, 5, 5, 5, 7, 8, 9, 10}
，從前往後周遊原始數組
A
中的元素。
第一次遇到107（
A[2]
count[6] = 5
，即第一個107在結果數組中的索引為5，即
result[5] = 107
count[6] = 6
第二次遇到107（
A[8]
count[6] = 6
，即第二個107在結果數組中的索引為6，即
result[6] = 107
count[6] = 7
public int[] countSort5(int[] A) {
// 找出數組A中的最大值、最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : A) {
max = Math.max(max, num);
min = Math.min(min, num);
}
// 初始化計數數組count
// 長度為最大值減最小值加1，再加1
int[] count = new int[(max-min+1)+1];
// 對計數數組各元素指派，count[0]永遠為0
for (int num : A) {
// A中的元素要減去最小值再加上1，再作為新索引
count[num-min+1]++;
}
// 計數數組變形，新元素的值是前面元素累加之和的值
for (int i=1; i<count.length; i++) {
count[i] += count[i-1];
}
// 建立結果數組
int[] result = new int[A.length];
// 周遊A中的元素，填充到結果數組中去，從前往後周遊
for (int j=0; j<A.length; j++) {
// 如果後面遇到相同的元素，在前面元素的基礎上往後排
// 如此就保證了原始數組中相同元素的原始排序
result[count[A[j]-min]] = A[j];
count[A[j]-min]++;
}
return result;
}
09 小結
以上就是計數排序算法的全部内容了，雖然它可以将排序算法的時間複雜度降低到
O(N)
，但是有兩個前提需要滿足：一是需要排序的元素必須是整數，二是排序元素的取值要在一定範圍内，并且比較集中。隻有這兩個條件都滿足，才能最大程度發揮計數排序的優勢。