基数排序
**基数排序(Radix Sort)**是一种非比较型整数排序算法。基数排序可以看作是桶排序的扩展,核心思想是将所有整数统一为位数相同的证书,位数较少的前面补零,然后按照位数切割,对每个位数分别进行比较和排序。
基数排序还分为了 LSD(Least significant digital) 和 **MSD(Most significant diagital)**两种实现方式。其中,LSD 先比较低位的数字,MSD 反之。
平均时间复杂度:
最好时间复杂度:
最坏时间复杂度:
最坏空间复杂度:
稳定性:稳定
排序方式:非原地(not-in-place)
LSD:
LSD 实现:
function radixSort(arr) {
const maxVal = Math.max(...arr);
const maxValLen = `${maxVal}`.length; // 最大的数的位数
// 补零
const _arr = arr.map((item) => `${item}`.padStart(maxValLen, '0'));
// 从低位开始对每一位进行比较后排序
for (let i = maxValLen - 1; i >=0; --i) {
_arr.sort((a, b) => parseInt(a[i], 10) - parseInt(b[i], 10));
}
// 赋值回 arr
_arr.forEach((item, index) => {
arr[index] = parseInt(item, 10);
});
return arr;
}
最后更新于