x-note
搜索文档…
Introduction
FE
正则表达式
Git
基础算法
冒泡排序
插入排序
选择排序
快速排序
归并排序
希尔排序
堆排序
桶排序
计数排序
基数排序
二叉树的遍历
HTTP
Protocol Buffers
gRPC
设计模式
由 GitBook 提供支持
基数排序
基数排序（Radix Sort）是一种非比较型整数排序算法。基数排序可以看作是桶排序的扩展，核心思想是将所有整数统一为位数相同的证书，位数较少的前面补零，然后按照位数切割，对每个位数分别进行比较和排序。
基数排序还分为了 LSD（Least significant digital） 和 MSD（Most significant diagital）两种实现方式。其中，LSD 先比较低位的数字，MSD 反之。
  • 平均时间复杂度：
    O(n∗k)\mathcal{O}(n * k)
    ​
  • 最好时间复杂度：
    O(n∗k)\mathcal{O}(n * k)
    ​
  • 最坏时间复杂度：
    O(n∗k)\mathcal{O}(n * k)
    ​
  • 最坏空间复杂度：
    O(n+k)\mathcal{O}(n + k)
    ​
  • 稳定性：稳定
  • 排序方式：非原地（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;
}
以前
计数排序
下一个
二叉树的遍历
最近更新 3yr ago
复制链接
在 GitHub 上编辑