计数排序是一个非基于比较的排序算法,该算法于 1954 年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为 Ο(n+k)(其中 k 是整数的范围),快于任何比较排序算法
算法评价
- 平均时间复杂度:O(n + k)
- 最好情况:O(n + k)
- 最坏情况:O(n + k)
- 空间复杂度:O(k)
- 稳定性:稳定
算法思想
- 找出待排序的数组中最大和最小的元素。
- 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第 i 项。
- 对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加)。
- 向填充目标数组:将每个元素 i 放在新数组的第 C[i] 项,每放一个元素就将 C[i] 减去 1。
代码示例
Javascript
Array.prototype.countSort = function() {
let len = this.length
if (len < 2) {
return
}
// 桶数组
var suportArr = new Array(len + 1);
// 结果数组
var resArr = new Array(len);
// 初始化桶数组
for (i = 0; i < suportArr.length; i++) {
suportArr[i] = 0;
}
// 待排序数组中的数组出现,在桶子对应位置+1代表这个数出现的个数+1了
for (let i = 0; i < len; i++) {
suportArr[arr[i]]++;
}
// 从第1项开始,桶数组加上前一个桶的个数,现在辅助数组的意义变成了每一项的排名了。
for (let i = 1; i < suportArr.length; i++) {
suportArr[i] += suportArr[i - 1];
}
// 根据辅助数组的排名,从后往前赋值
for (let i = len - 1; i >= 0; i--) {
resArr[suportArr[arr[i]] - 1] = arr[i];
suportArr[arr[i]]--;
}
// 这里this不能直接赋值数组,我们就只能采取splice剪切数组再替换新的
this.splice(0, this.length, resArr)
}