常见排序算法 - 基数排序 (Radix Sort)

2014-01-15 W.Y. 更多博文 » 博客 » GitHub »

原文链接 https://bubkoo.github.io/2014/01/15/sort-algorithm-radix-sort/
注：以下为加速网络访问所做的原文缓存，经过重新格式化，可能存在格式方面的问题，或偶有遗漏信息，请以原文为准。

算法原理

基数排序 (Radix Sort) 是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼在打孔卡片制表机 (Tabulation Machine)上的贡献。

排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序法会使用到桶 (Bucket)，顾名思义，通过将要比较的位（个位、十位、百位...），将要排序的元素分配至 0~9 个桶中，借以达到排序的作用，在某些时候，基数排序法的效率高于其它的比较性排序法。

Data Structure Visualizations 提供了一个基数排序的分步动画演示。

实例分析

基数排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital)，LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。以 LSD 为例，假设原来有一串数值如下所示：

   36   9   0   25   1   49   64   16   81   4

首先根据个位数的数值，按照个位置等于桶编号的方式，将它们分配至编号0到9的桶子中：

编号|0|1|2|3|4|5|6|7|8|9 ---|---|---|---|---|---|---|---|---|--- |0| 1 | | | 64|25 | 36| | |9 | | 81| | | 4| | 16| | |49 然后，将这些数字按照桶以及桶内部的排序连接起来：

   0   1   81   64   4   25   36   16   9   49

接着按照十位的数值，分别对号入座：

编号|0|1|2|3|4|5|6|7|8|9 ---|---|---|---|---|---|---|---|---|--- |0| 16| 25| 36| 49| | 64| | 81| |1| | | | | | | | | |4| | | | | | | | | |9| | | | | | | | |

最后按照次序重现连接，完成排序：

   0   1   4   9   16   25   36   49   64   81

JavaScript 语言实现

暴力上代码：

function radixSort(array) {
    var bucket = [],
        l = array.length,
        loop,
        str,
        i,
        j,
        k,
        t,
        max = array[0];

    for (i = 1; i < l; i++) {
        if (array[i] > max) {
            max = array[i]
        }
    }

    loop = (max + '').length;

    for (i = 0; i < 10; i++) {
        bucket[i] = [];
    }

    for (i = 0; i < loop; i++) {
        for (j = 0; j < l; j++) {
            str = array[j] + '';
            if (str.length >= i + 1) {
                k = parseInt(str[str.length - i - 1]);
                bucket[k].push(array[j]);
            } else { // 高位为 0
                bucket[0].push(array[j]);
            }
        }

        array.splice(0, l);
        for (j = 0; j < 10; j++) {
            t = bucket[j].length;
            for (k = 0; k < t; k++) {
                array.push(bucket[j][k]);
            }
            bucket[j] = [];
        }
    }
    return array;
}

算法原理

实例分析

JavaScript 语言实现

参考文章