演算法知識 - 基數排序 Radix Sort

Radix Sort 介紹與應用

Radix Sort 與我們一般常見的比較排序不同，採用分配式排序法(透過特定方式將值分別放入不同的 array)，Radix Sort 是特殊的整數排序法，Radix Sort 是根據每一位的數值放入相對應的 index。

時間複雜度為 \(O(dn)\)

Radix Array 原理

這裡用數字來舉範例，假設要排序的數值有：(1, 254 ,6932 ,24 )

• 先創建 10 個 queue，因為數字主要是透過 0~9 組合
• 從個位數開始進行排序，假設個位數是 1，則放入 queue[1]
• 從 queue[0] ~ queue[9] 開始依序將數值取出來並依序存入陣列
• 再來從十、百、千…位數開始進行排序，重複第二點及以下動作，直到沒有數值大於的位數。

名詞解釋：

• 位數
  指數字中某一特定數字字元(一個數字)所在的位置。EX:個位數、百分位

QUESTION: 為甚麼是從個位數開始進行排序？

如果從最大位數開始進行排序，會出現 8 > 126，變成了字典排序而不是順序排序，在百分位與十分位時都沒有問題，但到個分位時會變成 8 在比較後面的 queue，導致排序不正確。排序成 (126,8)

從最小位數開始依序排序，因為數學排序的邏輯是先根據位數進行排序才根據個數進行排序，
而 Radix Sort 排序則是權重越不高先排序，如果從最大位數排序則會變成字典順序。

Radix Sort 實作與說明

找出數列中最大的數，只要位數比他還小就直接跳出迴圈，剩下就與原理相同，直接在程式碼進行說明。

int num[10] = {24,6239 ,249 , 465935 , 4353 ,543 , 9352 ,2154 , 953 , 3952} ;

void radix_sort(){
    queue<int> buckets[10] ; // 創建存放位置
    // 如果是 0-9 就創建 10，A-Z(特別指大寫)就創建 26
    int k = 0 ,j = 1 ; // j 用來找出現在的位數
    for(int i = 0 ; i < 10 ; i++) k = max(num[i] , k );
    // k = 找出數列最大值 

    while(k/j){ //檢測還有沒有數值大於我們現在當下要檢測的位數
        // 如果沒有就代表已經檢測、排序完畢
        for(int i = 0 ; i < 10 ; i++) //將位數的值依序放入不同的 queue
            buckets[(num[i] /j)%10].push(num[i]); 
            //(num[i] /j)%10 找出當下位數的數值(一個數字)
        int p = 0 ; //p 排序位數的標準
        for(int i = 0 ; i < 10 ; i++){
            while(!buckets[i].empty()){ //直到這個 queue 沒有任何數字
                num[p++] =buckets[i].front(); // 將根據此位數排序的值放回 num 中
                // p++ 準備讓下一個值放入下一個位置
                buckets[i].pop(); //已經被放入 num 所以退出
            }
        }
        j *= 10; // 找下一個位數
    }
    for(int i = 0 ; i < 10 ;i++) // 輸出答案，檢測是否正確
        cout << i << ' ' << num[i] << '\n' ;
        cout << '\n' ;
}

放一份乾淨無註解的程式碼在此，方便讀者直接拿來使用

程式碼如下：

int num[10] = {24,6239 ,249 , 465935 , 4353 ,543 , 9352 ,2154 , 953 , 3952} ;

void radix_sort(){
    queue<int> buckets[10] ; 
    int k = 0 ,j = 1 ; 
    for(int i = 0 ; i < 10 ; i++) k = max(num[i] , k );

    while(k/j){ 
        for(int i = 0 ; i < 10 ; i++) 
            buckets[(num[i] /j)%10].push(num[i]); 
        int p = 0 ; 
        for(int i = 0 ; i < 10 ; i++){
            while(!buckets[i].empty()){ 
                num[p++] =buckets[i].front();
                buckets[i].pop();
            }
        }
        j *= 10;
    }
    for(int i = 0 ; i < 10 ;i++)
        cout << i << ' ' << num[i] << '\n' ;
        cout << '\n' ;
}

參考連結

基數排序 Radix sort
radix sort (基底排序法)
基數排序法

心得

老實講我排序學的沒有很多呀XD，那時候在比賽只練過幾個最有名氣的排序法後就直接去學習其他演算法，但當我學到 Suffix Array，卻發現自己不懂這個演算法阿阿阿阿阿，自己真爛。幸好有 Suffix Array 幫我補足過去的知識，由於我的演算法並不是透過專業的老師訓練而成，80% 都是透過我的自學而成，但自學有個很大的問題就是，容易基礎不紮實，很有可能在學到進階演算法時還要再回來補過去基礎。

不過沒關係，我會努力完成演算法的知識，我覺得學習演算法是一件很有趣的事情，它可以增加我的很多思維在我人生中都有稍微用到的時候，不敢說幫助很大，但至少學習的過程是不會後悔的。也希望我可以在參加 ICPC 時可以獲得好的名次，給予自己更大的信心與動力。