前面說的那些排序算法，都是要通過比較來實(shí)現(xiàn)的。排序還能不通過比較來實(shí)現(xiàn)？是的，計(jì)數(shù)排序就是這么神奇。

一、排序思想

創(chuàng)建一個(gè)計(jì)數(shù)數(shù)組，利用數(shù)組下標(biāo)來表示該元素，用數(shù)組下標(biāo)對(duì)應(yīng)的值來表示元素出現(xiàn)的次數(shù)。然后遍歷計(jì)數(shù)數(shù)組即可。比如下標(biāo)為5，元素值為2，表示5出現(xiàn)兩次，連續(xù)寫兩次5即可。

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

這樣看似很完美，但是會(huì)存在兩個(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)

• 接下來，對(duì)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è)元素都減去最小元素，得出來的值就對(duì)應(yīng)count的下標(biāo)。比如999 - 995 = 4，那么999就應(yīng)該對(duì)應(yīng)count[4]。

4. 計(jì)數(shù)排序的缺點(diǎn)：從上面的分析可以知道，計(jì)數(shù)排序適合分布比較集中的數(shù)據(jù)，即最大值和最小值相差不多，如果相差特別多，就會(huì)很耗費(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. 對(duì)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);
}