计数排序
- 平均时间复杂度:O(n+k)
- 最好情况:O(n+k)
- 最坏情况:O(n+k)
- 空间复杂度:O(k)
- 排序方式:Out-place
- 稳定性:稳定
算法步骤:
1.找出待排序的数组中最大值
2.统计数组中每个值为i的元素出现的次数，存入数组的第i项
3.对所有的计数累加
4.填充目标数组
function countSort(arr) {
//最大值的获取直接通过api获取
let maxValue = Math.max(...arr);
let len2 = maxValue + 1;
let arr2 = new Array(len2);
let index = 0;
let len = arr.length;
for (let i = 0; i < len; i++) arr2[arr[i]] = (arr2[arr[i]] || 0) + 1;
for (let j = 0; j < len2; j++) {
while (arr2[j] > 0) {
arr[index++] = j;
arr2[j]--;
}
}
}
网友评论