带你读《图解算法小抄》十四、排序（19）-阿里云开发者社区

带你读《图解算法小抄》十四、排序（19）

2023-10-12 63

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 带你读《图解算法小抄》十四、排序（19）

带你读《图解算法小抄》十四、排序（18）https://developer.aliyun.com/article/1348132?groupCode=tech_library

1）效率

基数排序与其他排序算法相比的效率问题有些棘手，并且容易引起很多误解。基数排序是否与最佳的基于比较的排序算法同样高效、低效还是更高效，取决于所做的具体假设。对于具有单词大小 w 的整数键的 n 个键，基数排序的复杂度为 O(wn)。有时将 w 视为常数，这将使基数排序（对于足够大的 n）优于最佳的基于比较的排序算法，因为所有这些排序算法对 n 个键进行排序时执行的比较次数为 O(n log n)。

然而，一般来说，w 不能被视为常数：如果所有的 n 个键都是不同的，那么为了能够在内存中存储它们，w 必须至少为 log n，这最多可以给出时间复杂度为 O(n log n)。这似乎使基数排序最多与最佳的基于比较的排序算法同样高效（如果键比 log n 长很多，则效率会更低）。

基数排序

2）原理：

基数排序是一种多次分配和收集的排序算法。它按照位数进行排序，从最低有效位（个位）到最高有效位（最高位）。具体排序流程如下：

步骤1：将待排序的整数序列按照个位数进行排序，形成个位数上的桶；
步骤2：按照十位数将桶中的元素收集起来，形成十位数上的桶；
步骤3：重复上述步骤，直到最高有效位。

重复这个过程后，整个序列将按照位数从低到高逐渐有序。

function radixSort(arr) {
  const max = Math.max(...arr); // 获取数组中的最大值
  const maxDigitCount = digitCount(max); // 获取最大值的位数
  for (let i = 0; i < maxDigitCount; i++) {
    const digitBuckets = Array.from({ length: 10 }, () => []);
    for (let j = 0; j < arr.length; j++) {
      const digit = getDigit(arr[j], i + 1);
      digitBuckets[digit].push(arr[j]);
    }
    arr = [].concat(...digitBuckets);
  }
  return arr;
}
// 获取数字的位数function digitCount(num) {
  if (num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}
// 获取数字指定位数上的值function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place - 1)) % 10;
}

带你读《图解算法小抄》十四、排序（20）https://developer.aliyun.com/article/1348130?groupCode=tech_library

带你读《图解算法小抄》十四、排序（19）

1）效率

2）原理：

开发者学习资源库

热门文章

最新文章

相关课程

相关电子书

相关实验场景