61 lines
1.7 KiB
JavaScript
61 lines
1.7 KiB
JavaScript
/**
|
||
* @description 计数排序, 只能对大于零的整数排序
|
||
* @param {number[]} arr - 需要排序的数组
|
||
*/
|
||
export function countSort(arr) {
|
||
const len = arr.length;
|
||
const counts = []; // 用于计数的数组
|
||
// 遍历整个数组
|
||
for (let i = 0; i < len; i++) {
|
||
const el = arr[i];
|
||
counts[el] = counts[el] ? counts[el] + 1 : 1;
|
||
}
|
||
let index = 0;
|
||
for (let i = 0; i < counts.length; i++) {
|
||
let time = counts[i];
|
||
while (time) {
|
||
// 当桶子不为空时，遍历time次
|
||
arr[index++] = i;
|
||
time--;
|
||
}
|
||
}
|
||
return arr; // 返回与不反都可以，本身就是对原数组的操作
|
||
}
|
||
|
||
/**
|
||
* @description 修改后的计数排序，支持负数
|
||
* @param {number[]} arr - 要排序的整数数组
|
||
*/
|
||
export function countSort2(arr) {
|
||
// 先找出最大值和for
|
||
const n = arr.length;
|
||
let min = arr[0];
|
||
let max = arr[0];
|
||
for (let i = 0; i < n; i++) {
|
||
if (arr[i] > max) {
|
||
max = arr[i];
|
||
}
|
||
if (arr[i] < min) {
|
||
min = arr[i];
|
||
}
|
||
}
|
||
// 计算计数数组的大小
|
||
const size = max - min + 1;
|
||
const counts = new Array(size).fill(0);
|
||
// 遍历原数组把"值-min"作为计数数组的下标, 值-min能保证下标永 远不会小于零
|
||
for (let i = 0; i < n; i++) {
|
||
counts[arr[i] - min]++;
|
||
}
|
||
// 遍历counts数组， 累计前面的下下标值
|
||
for (let i = 1; i < size; i++) {
|
||
counts[i] += counts[i - 1];
|
||
}
|
||
const ret = [];// 排序后的新数组
|
||
// 现在数组的下表就是值，值就是下标
|
||
for (let i = n - 1; i >= 0; i--) {
|
||
counts[arr[i] - min]--; // 假设我们有三个数放入counts中，counts[0]=1,counts[1]=2,counts[2]=3,所以要先减1再做下标使用
|
||
ret[counts[arr[i] - min]] = arr[i];
|
||
}
|
||
return ret;
|
||
}
|