計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中恢着。 作為一種線性時(shí)間復(fù)雜度的排序菜拓，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)蹬跃。
計(jì)數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法。計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C厢呵，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)窝撵。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置。它只能對(duì)整數(shù)進(jìn)行排序襟铭。
算法描述
找出待排序的數(shù)組中最大和最小的元素碌奉；
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)寒砖；
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開始赐劣，每一項(xiàng)和前一項(xiàng)相加）；
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)入撒，每放一個(gè)元素就將C(i)減去1隆豹。
算法分析：
時(shí)間復(fù)雜度
最佳情況：T(n) = O(n+k) 最差情況：T(n) = O(n+k) 平均情況：T(n) = O(n+k)
當(dāng)輸入的元素是n 個(gè)0到k之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是 O(n + k)茅逮。計(jì)數(shù)排序不是比較排序璃赡，排序的速度快于任何比較排序算法。由于用來計(jì)數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1）献雅，這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組碉考，需要大量時(shí)間和內(nèi)存。
public static int[] CountingSort(int[] array) {
if (array.length == 0) return array;
int bias, min = array[0], max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max)
max = array[i];
if (array[i] < min)
min = array[i];
}
bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0; i < array.length; i++) {
bucket[array[i] + bias]++;
}
int index = 0, i = 0;
while (index < array.length) {
if (bucket[i] != 0) {
array[index] = i - bias;
bucket[i]--;
index++;
} else
i++;
}
return array;
}
