59 lines
1.9 KiB
JavaScript
59 lines
1.9 KiB
JavaScript
import insertionSort from './insertion-sort.mjs';
|
||
|
||
/**
|
||
* 使用lsd基数排序
|
||
* @param {number[]} arr - 要基数排序的数组
|
||
*/
|
||
function radixSort(arr) {
|
||
let max = Math.abs(Math.max(...arr)); // 拿取数组中最大的数，用于计算长度
|
||
let buckets = Array.from({ length: 10 }, () => []);
|
||
let curDit = 1; // 当前比较的是哪个数位 1表示个位
|
||
/* 处理负数，思路： 把所有的负数和正数都分开，负数使用绝对值处理之后以同样的方法处理，处理完之后取相反数再
|
||
倒序添加到原数组的前面
|
||
*/
|
||
let negativeArr = [];
|
||
const tempArr = [];
|
||
for (let i = 0; i < arr.length; i++) {
|
||
const temp = arr[i];
|
||
if (temp < 0) {
|
||
negativeArr.push(temp);
|
||
} else {
|
||
tempArr.push(temp);
|
||
}
|
||
}
|
||
arr = tempArr;
|
||
if (negativeArr.length) negativeArr = radixSort(negativeArr.map((_) => -_)).map((_) => -_);
|
||
while (Math.floor(max)) {
|
||
for (let i = 0; i < arr.length; i++) {
|
||
buckets[getNumByGidit(arr[i], curDit)].push(arr[i]); // 根据数位的大小放入对应的数位桶中
|
||
}
|
||
// 对buckets中的每个桶的元素做好排序，这里我们调用之前的插入排序
|
||
for (let i = 0; i < buckets.length; i++) {
|
||
insertionSort(buckets[i]);
|
||
}
|
||
// 个位比较完成之后比较十位，在此之前要把个位有序的数组给原数组,并且把桶子清空
|
||
arr = buckets.flat();
|
||
buckets = Array.from({ length: 10 }, () => []);
|
||
max /= 10; // 处理下一数位
|
||
curDit++;
|
||
}
|
||
return negativeArr.length ? negativeArr.reverse().concat(arr) : arr;
|
||
}
|
||
|
||
/**
|
||
* @description 获取某位的数字
|
||
* @param {number} num - 传入的数值
|
||
* @param {number} dit - 要获取的位数
|
||
*/
|
||
function getNumByGidit(num, dit) {
|
||
if (!num) return 0;
|
||
let res = 0;
|
||
while (dit--) {
|
||
res = num % 10;
|
||
num = (num - res) / 10;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
export default radixSort;
|