JavaScript 数据结构与算法之美 - 十大经典排序算法汇总（下）

3.10 基数排序（Radix Sort）

思想

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

例子

假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢 ？

这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。所以是基于位来比较的。

桶排序、计数排序能派上用场吗 ？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢 ？ 有，就是基数排序。

使用条件

• 要求数据可以分割独立的位来比较；
• 位之间由递进关系，如果 a 数据的高位比 b 数据大，那么剩下的地位就不用比较了；
• 每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到 O(n)。

方案

按照优先从高位或低位来排序有两种实现方案:

• MSD：由高位为基底，先按 k1 排序分组，同一组中记录, 关键码 k1 相等，再对各组按 k2 排序分成子组, 之后，对后面的关键码继续这样的排序分组，直到按最次位关键码 kd 对各子组排序后，再将各组连接起来，便得到一个有序序列。MSD 方式适用于位数多的序列。
• LSD：由低位为基底，先从 kd 开始排序，再对 kd - 1 进行排序，依次重复，直到对 k1 排序后便得到一个有序序列。LSD 方式适用于位数少的序列。

实现

/**
    * name: 基数排序
    * @param  array 待排序数组
    * @param  max 最大位数
    */
const radixSort = (array, max) => {
    console.time('计数排序耗时');
    const buckets = [];
    let unit = 10,
        base = 1;
    for (let i = 0; i < max; i++, base *= 10, unit *= 10) {
        for (let j = 0; j < array.length; j++) {
            let index = ~~((array[j] % unit) / base); //依次过滤出个位，十位等等数字
            if (buckets[index] == null) {
                buckets[index] = []; //初始化桶
            }
            buckets[index].push(array[j]); //往不同桶里添加数据
        }
        let pos = 0,
            value;
        for (let j = 0, length = buckets.length; j < length; j++) {
            if (buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                    array[pos++] = value; //将不同桶里数据挨个捞出来，为下一轮高位排序做准备，由于靠近桶底的元素排名靠前，因此从桶底先捞
                }
            }
        }
    }
    console.timeEnd('计数排序耗时');
    return array;
};

测试

const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log('原始array:', array);
const newArr = radixSort(array, 2);
console.log('newArr:', newArr);
// 原始 array:  [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
// 堆排序耗时:   0.064208984375ms
// newArr:       [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

分析

• 第一，基数排序是原地排序算法吗 ？

因为计数排序的空间复杂度为 O(n + k)，所以不是原地排序算法。

• 第二，基数排序是稳定的排序算法吗 ？

基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。

• 第三，基数排序的时间复杂度是多少 ？

最佳情况：T(n) = O(n * k)

最差情况：T(n) = O(n * k)

平均情况：T(n) = O(n * k)

其中，k 是待排序列最大值。

动画

LSD 基数排序动图演示：

4. 复杂度对比

十大经典排序算法的 时间复杂度与空间复杂度 比较。

名词解释：

• n：数据规模；
• k：桶的个数；
• In-place: 占用常数内存，不占用额外内存；
• Out-place: 占用额外内存。

5. 算法可视化工具

• 算法可视化工具 algorithm-visualizer

算法可视化工具 algorithm-visualizer 是一个交互式的在线平台，可以从代码中可视化算法，还可以看到代码执行的过程。旨在通过交互式可视化的执行来揭示算法背后的机制。

效果如下图：

• 算法可视化动画网站 https://visualgo.net/en

效果如下图：

• 算法可视化动画网站 www.ee.ryerson.ca

效果如下图：

• illustrated-algorithms

变量和操作的可视化表示增强了控制流和实际源代码。您可以快速前进和后退执行，以密切观察算法的工作方式。

效果如下图：