带你读《图解算法小抄》十四、排序（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
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)