今天來講一個「非比較性」的演算法，基數排序法 (Radix Sort)。其實之前的排序法也是屬於 非比較性 的演算法。怎麼說？以泡沫和快速為例，這兩個演算法都是要將資料裡的值，透過兩倆相互比較大小進而排序。而 非比較性 的排序則是屬於「分配性」的方式，是利用資料裡的值的某些特性來作為排序的依據，而非是用比較的方式。

舉個例子。

一樣有份資料要做排序：

左　<-------------------------------------------------------------------------------　右

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

在排序前，有兩種排序方式可以參考。一種是 MSD(Most Significant Digit)，另一種是 LSD(Least Significant Digit)。這兩種方式都是依據鍵值的的方向來做處理。LSD 從鍵值的最右邊開始，MSD 則是從最左邊開始。下面以 LSD 為例。

首先我們先從資料的個位數開始來分配。

利用桶子的概念分至 0 到 9 好的桶子。

接著將數值串連起來。

data = [100, 92, 23, 23, 34, 55, 66, 96, 96, 67, 78, 78, 88, 89, 29, 79]

接著再從十位數分配。

接著將數值串連起來。

data = [100, 23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96]

繼續從百位數分配。

接著將數值串連起來。

data = [23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

終於完成了～～這就是三位數的範例。如果位數更多的話，就要重複做以上動作到最高位。
LSD 是從鍵值的最邊開始，所以適合位數小的資料來做排序。MSD 則相反，從最左邊，也就是最高位數來開始排序。
如果位數很多的話，其實 MSD 會來得更有效率一些。

全部程式碼：

程式時間複雜度：Ｏ(kN)，k 取決於位元的位數。

data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

# Radix sort
def radixsort(data):
    length = len(data)
    count = max(data) # 資料裡最大的數值

    # 用最大數來判斷最大位數
    digit = 1
    while count > 9:
        count /= 10
        digit += 1

    tmp = []
    cur = 0
    for i in range(length):    # 資料的大小會決定桶子的數量，會是一個二維陣列
        tmp.append([0] * length)
    order = [0] * length       # 游標行，用來將資料放到同一位數但不同列的桶子

    if digit <= 9:
        '''use LSD(Least significant digit) method '''
        n = 1
        while n <= max(data):
            for i in range(length):
                lsd = int(data[i]/n) % 10  # 將資料用10來取個位數的餘數
                tmp[lsd][order[lsd]] = data[i]
                order[lsd] += 1
            for i in range(length):
                # 如果這個位數的桶子在此行有資料，就丟到同一個位數，但下一列的位置
                if order[i] != 0:
                    for j in range(order[i]):
                        data[cur] = tmp[i][j]
                        cur += 1
                # 將游標行的資料歸零
                order[i] = 0
            n *= 10
            cur = 0
        print(data)
        
radixsort(data)

拉蒙碎碎念

在某些時候，其實基數排序法可以比快速排序法要快。因為快速排序是用兩兩比較的方式，但如果資料量大的時候就必須執行非常多輪。而基數排序則不會。之後有機會再寫一篇來討論有關程式的時間和空間的複雜度吧。

其實懂這個做法的邏輯後，可以試著自己挑戰 MSD 看看。上面的範例我用 9 位數來做 LSD 和 MSD 的分界。程式一樣可以執行，其他的就交給讀著動手做囉。