iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 4
0

今天來講一個「非比較性」的演算法,基數排序法 (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 好的桶子。

0 1 2 3 4 5 6 7 8 9
23 96
92 96 88
55 78 79
100 23 34 66 67 78 29
89

接著將數值串連起來。

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

接著再從十位數分配。

0 1 2 3 4 5 6 7 8 9
29 79 89
78 88
67 78 96
23 34 55 66 96
100 23 92

接著將數值串連起來。

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

繼續從百位數分配。

0 1 2 3 4 5 6 7 8 9
96
96
92
89
88
79
78
78
67
66
55
34
29
23
23
100

接著將數值串連起來。

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

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

全部程式碼:

程式時間複雜度:O(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 的分界。程式一樣可以執行,其他的就交給讀著動手做囉。


上一篇
[演算法] 快速排序法 (Quick Sort)
下一篇
[演算法] 列舉法 (Enumeration)
系列文
30天學演算法和資料結構31

尚未有邦友留言

立即登入留言