計(jì)數(shù)排序不是基于比較的排序算法星压，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。 作為一種線性時(shí)間復(fù)雜度的排序鬼譬，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)娜膘。
8.1 算法描述
- 找出待排序的數(shù)組中最大和最小的元素；
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)优质，存入數(shù)組C的第i項(xiàng)劲绪；
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）盆赤；
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1歉眷。
8.2 動(dòng)圖演示
image
8.3 代碼實(shí)現(xiàn)
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
8.4 算法分析
計(jì)數(shù)排序是一個(gè)穩(wěn)定的排序算法牺六。當(dāng)輸入的元素是 n 個(gè) 0到 k 之間的整數(shù)時(shí)，時(shí)間復(fù)雜度是O(n+k)汗捡，空間復(fù)雜度也是O(n+k)淑际，其排序速度快于任何比較排序算法。當(dāng)k不是很大并且序列比較集中時(shí)扇住，計(jì)數(shù)排序是一個(gè)很有效的排序算法春缕。
