计数排序是一种线性时间复杂度的排序算法，不需要进行元素之间的比较，只适合处理一定范围内的整数排序场景，在JavaScript中实现计数排序逻辑清晰，实用性较强。
计数排序的核心原理
计数排序的核心思路是：先统计待排序数组中每个元素出现的次数，然后根据统计结果，将元素按顺序回填到原数组或者新数组中完成排序。它要求待排序的元素都是整数，并且元素的范围不能太大，否则会占用过多的额外空间。
计数排序是稳定排序，相同元素的相对顺序在排序后不会改变，这一点在对对象按照某个整数属性排序时非常有用。
JavaScript实现计数排序的步骤
实现计数排序主要分为以下几个步骤：
- 遍历待排序数组，找到数组中的最大值和最小值，确定元素的范围
- 创建一个计数数组，长度为最大值减去最小值加一，用来统计每个元素出现的次数
- 再次遍历待排序数组，针对每个元素，将计数数组中对应位置的值加一
- 对计数数组做前缀和处理，这样每个位置的值就表示该元素排序后应该放置的最后位置
- 从后往前遍历待排序数组，根据计数数组的结果将元素放到结果数组的对应位置，同时更新计数数组的值，保证稳定性
- 将结果数组拷贝回原数组，完成排序
完整JavaScript实现代码
下面是支持整数范围、保证稳定性的计数排序完整实现：
/**
* JavaScript计数排序实现
* @param {number[]} arr 待排序的整数数组
* @returns {number[]} 排序后的数组
*/
function countingSort(arr) {
if (arr.length <= 1) {
return arr;
}
// 找到数组的最小值和最大值
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
// 创建计数数组，长度为max - min + 1
const countLen = max - min + 1;
const countArr = new Array(countLen).fill(0);
// 统计每个元素出现的次数
for (let i = 0; i < arr.length; i++) {
const index = arr[i] - min;
countArr[index]++;
}
// 计数数组做前缀和处理
for (let i = 1; i < countLen; i++) {
countArr[i] += countArr[i - 1];
}
// 创建结果数组，从后往前遍历保证稳定性
const result = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
const index = arr[i] - min;
const position = countArr[index] - 1;
result[position] = arr[i];
countArr[index]--;
}
// 将结果拷贝回原数组
for (let i = 0; i < arr.length; i++) {
arr[i] = result[i];
}
return arr;
}
// 测试示例
const testArr = [4, 2, 8, 2, 5, 1, 4, 6];
console.log("排序前：", testArr);
countingSort(testArr);
console.log("排序后：", testArr);计数排序的复杂度与适用场景
计数排序的时间复杂度为O(n + k)，其中n是待排序数组的长度，k是元素的范围大小；空间复杂度为O(k + n)，需要额外的计数数组和结果数组。
它的适用场景非常明确：
- 待排序元素都是整数
- 元素的范围k不是特别大，否则会浪费大量空间
- 需要稳定排序的场景，比如按照年龄排序用户对象时，相同年龄的用户保持原有顺序
如果待排序的元素是浮点数，或者元素范围非常大（比如从1到1000000只有10个元素），就不适合使用计数排序，此时可以选择快速排序、归并排序等其他算法。
常见问题说明
很多开发者会疑惑为什么要从后往前遍历原数组放元素，这是因为计数排序要保证稳定性，从后往前遍历可以让相同元素按照原来的相对顺序放入结果数组。如果不需要稳定性，也可以从前往后遍历，不过大多数场景下建议保留稳定性，适用范围更广。
另外如果待排序数组的元素都是正整数，也可以简化实现，不需要处理最小值，计数数组长度直接为最大值加一，不过支持最小值的实现能处理包含负整数的场景，通用性更强。
计数排序JavaScript排序算法稳定排序时间复杂度线性排序修改时间：2026-05-29 22:39:59