基數排序(Radix Sort)演算法是可以利用多個鍵值來排序資料的演算法。排序還需要多個鍵值?有時候當然會需要啦!像是要排序檔案時,可以先依照檔案名稱排序後,再依照檔案大小來排,如此一來,整體上來看這些檔案,會是以檔案大小來排序,而相同檔案大小的檔案則是會依照檔案名稱來排序。基數排序法可以將整數的各個位數當作是鍵值,來進行線性時間的排序,比起會依照k(要排序的資料可能的值的數量)愈大而愈吃空間的計數排序法,基數排序法的空間複雜度是比較能夠控制的。



基數排序法(Radix Sort)

基數排序法的概念

基數排序法將整數的各個位數當作是鍵值,可以進行數值上遞增、遞減的排序,如:[1, 2, 3, 12, 23];或是進行辭典排序,如[1, 12, 2, 23, 3]

若我們從整數最小的位數(LSD, least significant digit)開始,先把個位數當鍵值來排序、再把十位數當鍵值來排序、再把百位數當鍵值來排序……依此類推,直到完成最高位數的排序之後,就可以排出遞增或是遞減的序列了!若我們從整數最大的位數(MSD, most significant digit)開始,排到最小的個位數,就會是辭典排序。這邊要特別注意的是,從MSD開始排序的時候,從左邊往右開始數的第一個有效位數就是MSD,例如82088的MSD,220的MSD;從LSD開始排序的時候,從右邊往左開始數的第一個有效位數就是LSD,例如82088的LSD,020的LSD。

以程式實作面來說,LSD的基數排序法比MSD的基數排序法還更容易實現。

基數排序法的過程

LSD──遞增或遞減排序

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

首先我們先拿個位數當鍵值,使用計數排序等適合少量已知數值範圍資料且穩定的演算法,先將序列進行第一次的遞增排序。這邊要注意的是,若有元素的位數小於整個序列的元素的最高位數時,要從最高位數開始補0

索引    0   1   2   3   4   5   6   7   8   9
數值    6   8   3   3   0   0   4   6   3   7
        9   1   0   8   9   2   7   1   2   9   ●

排序後的結果如下:

索引    0   1   2   3   4   5   6   7   8   9
數值    3   8   6   0   3   4   3   6   0   7   ●
        0   1   1   2   2   7   8   9   9   9   ○

再來繼續排序十位數,排序後的結果如下:

索引    0   1   2   3   4   5   6   7   8   9
數值    0   0   3   3   3   4   6   6   7   8   ○
        2   9   0   2   8   7   1   9   9   1   ○

由於此序列最高位數就是十位數,至此就排序完成啦!

radix-sort

MSD──辭典排序

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何以辭典排列原則將它排序完成呢?

這邊會需要用到額外的空間。利用十個桶子,編號為0~9,把目前正在查看的位數是0~9的元素個別丟進這十個桶子內。如果該位數的值是0,就丟進0號桶子;如果該位數的值是5,就丟進5號桶子,依此類推。

桶子號碼    0   1   2   3   4   5   6   7   8   9
桶子內容   []  []  []  []  []  []  []  []  []  []

一開始當然是先看MSD,把元素依據MSD丟入桶子中之後,桶子的內容此時如下:

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
        
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 38, 32]          [47]            []      [69, 61]          [79]          [81]            [9]

接著開始走訪所有桶子,尋找所有元素數量大於1的桶子,因為它們還需要再分類!

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ●
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 38, 32]          [47]            []      [69, 61]          [79]          [81]            [9]

我們可以先找到號碼3的桶子,它擁有三個元素。接著我們再拿十個新桶子出來,編號為0~9,把原先十個桶子中號碼3的桶子內的所有元素再分進去,此時要看的位數是目前位數(也就是MSD)的下一個位數。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [30, 38, 32]
        
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容     [30]            []            []          [32]            []            []            []            []          [38]             []

同樣地,開始走訪所有桶子,尋找所有元素數量大於1的桶子,因為它們還需要再分類!

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [30, 38, 32]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容     [30]            []            []          [32]            []            []            []            []          [38]             []

因為已經沒有元素數量大於1的桶子了,就把這個桶子堆2的所有元素,再按照桶子順序塞回原本在桶子堆1的號碼3的桶子中。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [69, 61]          [79]          [81]            [9]

接著繼續尋找元素數量大於1的桶子吧!

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ●
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [69, 61]          [79]          [81]            [9]

我們可以找到號碼6的桶子,它擁有兩個元素。接著我們再拿十個新桶子出來,編號為0~9,把原先十個桶子中號碼6的桶子內的所有元素再分進去,此時要看的位數是目前位數(也就是MSD)的下一個位數。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [69, 61]
        
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []          [61]            []            []            []            []            []            []            []           [69]

同樣地,開始走訪所有桶子,尋找所有元素數量大於1的桶子,因為它們還需要再分類!

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79] -> [69, 61]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []          [61]            []            []            []            []            []            []            []           [69]

因為已經沒有元素數量大於1的桶子了,就把這個桶子堆3的所有元素,再按照桶子順序塞回原本在桶子堆1的號碼6的桶子中。

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]            [9]

接著繼續尋找元素數量大於1的桶子吧!

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]            [9]

因為已經沒有元素數量大於1的桶子了,就把這個桶子堆1的所有元素,按照桶子順序串接起來吧!

[69, 81, 30, 38, 9, 2, 47, 61, 32, 79]
               ○            ○            ○            ○            ○            ○            ○            ○            ○             ○
桶子號碼        0             1             2             3             4             5             6             7             8              9
桶子內容       []            []           [2]  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]            [9]
              └───────────────────────────────┬───────────────────────────────┘
                                                             [2, 30, 32, 38, 47, 61, 69, 79, 81, 9]

可以直接用原陣列來儲存串接結果,如此一來陣列就排序完成了!

radix-sort

基數排序法的實作

LSD──遞增和遞減排序

這邊的程式實作是以非常通用的方式來完成,一開始會先找出陣列元素中的最大值,為了拿來判斷目前是否已經看到最高位數。因為輸入的元素有可能會是負數的,所以在尋找最大值的時候要以元素的絕對值為準。另外,計數排序法的部份,會建立出長度為19的計數陣列,這是因為一個位數可能的值為-9 ~ +9,共19種可能。((n / digit) % 10) + 9這個算式是先計算出目前要看的位數的值之後,再進行-(-9)的索引值位移。

MSD──十進制辭典排序(穩定排序)

這邊的程式實作是以非常通用的方式來完成,為了要能夠排序正數和負數,因此在最一開始,會先將陣列元素分為負數和正數兩個桶子,再分別對這兩個桶子進行從MSD開始的排序。在桶子堆的桶子數量方面,這邊的程式是使用11個,而不是10個,多出來的那個(索引編號為0)是用來儲存位數比較少的元素,如此一來在遇到[40, 4]的時候,4才會在40的前面,當然,如果沒有要這麼嚴格要求這類的順序的話,一個桶子堆是可以只用10個桶子的!

基數排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。以#{{d}}#來表示數值的位數。以#{{k}}#來表示要排序的資料(鍵值)可能的值的數量,在此即為基數。

項目備註
最差時間複雜度LSD:#{{O((n + k) \times d)}}#
穩定MSD:#{{O(n \times d)}}#
穩定計數排序法的複雜度再乘以數值的位數。
所有元素都相等時。
最佳時間複雜度LSD:#{{O((n + k) \times d)}}#
穩定MSD:#{{O(n)}}#
穩定計數排序法的複雜度再乘以數值的位數。
所有元素的MSD都不相同。
平均時間複雜度LSD:#{{O((n + k) \times d)}}#
穩定MSD:#{{O(n \times d)}}#
穩定計數排序法的複雜度再乘以數值的位數。
額外最差空間複雜度LSD:#{{O(n + k)}}#
穩定MSD:#{{O((n + k) \times d)}}#
穩定計數排序法的額外空間。
所有元素都相等時,每次的位數檢查都會產生#{{k}}#個桶子,且其中有一個的桶子空間都會是#{{n}}#。可用LinkedList結構來優化成#{{O(n + k)}}#。
是否穩定LSD:是
穩定MSD:是
聽說原地的MSD基數排序法是不穩定的。