x-note
Search…
计数排序
计数排序(Counting sort)是一种稳定的线性时间排序算法。计数排序使用一个长度为maxVal - minVal + 1的额外的数据结构
C\mathcal{C}
,其中第 i 个元素是待排序数组
A\mathcal{A}
中值等于 i 的元素个数。然后根据数组
C\mathcal{C}
来将
A\mathcal{A}
的元素排到正确的位置。
计数排序本质上是一种特殊的桶排序,当桶的个数最大的时候,就是计数排序。
  • 平均时间复杂度:
    O(n+k)\mathcal{O}(n + k)
  • 最好时间复杂度:
    O(n+k)\mathcal{O}(n + k)
  • 最坏时间复杂度:
    O(n+k)\mathcal{O}(n + k)
  • 空间复杂度:
    O(n+k)\mathcal{O}(n + k)
  • 稳定性:稳定
  • 排序方式:非原地(not-in-place)
k=maxValminValk = maxVal - minVal
, 为最大值和最小值的差值。也就是说,当最大值和最小值相差过大,但是数组数量较小时,不应采用计数排序
算法步骤: 1. 找出待排序的数组中最大和最小的元素 2. 统计数组
A\mathcal{A}
中每个值为 i 的元素出现的次数,存入数组
C\mathcal{C}
的第 i 项 3. 对所有的计数累加(从
C\mathcal{C}
中的第一个元素开始,每一项和前一项相加) 4. 反向填充目标数组:将每个元素 i 放在新数组的第
C[i]\mathcal{C}[{i}]
项,每放一个元素就将
C[i]\mathcal{C}[{i}]
减去 1
JavaScript 实现:
function countingSort(arr) {
// JavaScript 数组本身就是动态分配的内存,
// 对于 JavaScript 简略版本,完全可以不去考虑额外结构内存分配,
let minVal = Math.min(...arr);
let maxVal = Math.max(...arr);
const c = new Array(maxVal - minVal + 1);
// const c = [];
arr.forEach(item => {
let index = item - minVal;
let counter = c[index];
c[index] = counter ? counter + 1 : 1;
})
arr.splice(0); // 清空数组
c.forEach((item, index) => {
while(item) {
arr.push(index + minVal);
item --;
}
});
return arr;
}
Copy link