（11）基數(shù)排序 (Radix Sort)

算法原理

基數(shù)排序 (Radix Sort) 是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較?；鶖?shù)排序的發(fā)明可以追溯到 1887 年赫爾曼·何樂(lè)禮在打孔卡片制表機(jī) (Tabulation Machine)上的貢獻(xiàn)。

排序過(guò)程：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列。

基數(shù)排序法會(huì)使用到桶 (Bucket)，顧名思義，通過(guò)將要比較的位（個(gè)位、十位、百位…），將要排序的元素分配至 0~9 個(gè)桶中，借以達(dá)到排序的作用，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。

Data Structure Visualizations?提供了一個(gè)基數(shù)排序的分步動(dòng)畫演示。

實(shí)例分析

基數(shù)排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital)，LSD 的排序方式由鍵值的最右邊開始，而 MSD 則相反，由鍵值的最左邊開始。 以 LSD 為例，假設(shè)原來(lái)有一串?dāng)?shù)值如下所示：

36   9   0   25   1   49   64   16   81   4

首先根據(jù)個(gè)位數(shù)的數(shù)值，按照個(gè)位置等于桶編號(hào)的方式，將它們分配至編號(hào)0到9的桶子中：

然后，將這些數(shù)字按照桶以及桶內(nèi)部的排序連接起來(lái)：

0   1   81   64   4   25   36   16   9   49

接著按照十位的數(shù)值，分別對(duì)號(hào)入座：

最后按照次序重現(xiàn)連接，完成排序：

0   1   4   9   16   25   36   49   64   81

JavaScript 語(yǔ)言實(shí)現(xiàn)

暴力上代碼：

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

參考文章

• 維基百科，自由的百科全書
• Data Structure Visualizations
• Algorithm Gossip: 基數(shù)排序法
• Radix Sorting