排序算法的详细介绍(十一) -- 基数排序

常见排序算法归档介绍:

基数排序 Radix Sort

算法描述

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

实例分析

数组: [36, 9, 0, 25, 1, 49, 64, 16, 81, 4], 排序过程:

36   9   0   25   1   49   64   16   81   4

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

radix_sort_step1

0   1   81   64   4   25   36   16   9   49

接着按照十位的数值,分别对号入座:

radix_sort_step2

0   1   4   9   16   25   36   49   64   81

代码实现

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;
}

此文参考于 bubkoo.com,十分感谢.
所有引用内容版权归原作者所有.
使用知识共享“署名-非商业性使用-相同方式共享 3.0 中国大陆”许可协议授权.

常见排序算法归档介绍:

基数排序 Radix Sort

算法描述

实例分析

代码实现

CATALOG

FEATURED TAGS