[演算法(Algorithm)] 基數排序(Radix Sort)

• 基數排序
  
  
  
  • 又叫基底排序、Bin Sort、Bucket Sort
  
  
  • 是一種分配式排序(Distribution Sort)
  
  
  • 可以多鍵值排序
    
    
    
    • 兩個鍵值：(1,2), (2,2), (3,1),...
    
    
    • 撲克牌(花色、數值)：(♠7), (♥7), (♣6), (♦3)
    
    

    
    

  
  
  • 只有一個鍵值時，可以利用分解鍵值來進行基數排序
  
  
  • 將數值切割以進行排序
    
    
    
    • 92 = 9, 2
    
    
    • 173 = 1, 7, 3
    
    

    
    

  
  
  • 利用桶子(Bucket)來分類
  
  
  • 以r為基底(Base)時，需準備r個桶子  數值時，基底即為進制
    
    • 排序10進位數字，需10個桶子
    
    

  
  
  • 資料的位數即為執行的回合數
    
    
    
    • 數值的範圍在0~9內，需執行1回合
    
    
    • 數值的範圍在0~99內，需執行2回合
    
    
    • 數值的範圍在0~999內，需執行3回合
    
    

    
    

  
  

  
  



• LSD & MSD
  
  
  
  • LSD(Least Significant Digital)
    
    
    
    • 由右到左
    
    
    • 173，依序用3,7,1來分類
    
    

    
    

  
  
  • MSD(Most Significant Digital)
    

    
    
    • 由左到右
    
    
    • 173，依序用1,7,3來分類
    
    

    
    

  
  

  
  



• 基數排序作法
  
  
         

  
             
  • RadixSort(LSD)
  
             
  • RadixSort(MSD)
             
             
         

  
             

  
             

  
             
  1. 選定好本回合使用的基數
  
  
  2. 依序用基數對每一筆資料取得該回合的LSD
  
  
  3. 依取得的LSD將資料放到對應的桶子中
  
  
  4. 依桶子內存放的順序，將資料回存原來的陣列
  
  
  5. 重複上面四個步驟，直到範圍內的基數皆已使用
  
  

  
             

             

  
             

  
             
  1. 選定好本回合使用的基數
  
  
  2. 依序用基數對每一筆資料取得該回合的MSD
  
  
  3. 依取得的MSD將資料放到對應的桶子中
  
  
  4. 依序對每個桶子重複上述三個步驟(遞迴)，直到範圍內的基數皆已使用
  
  
  5. 依桶子內存放的順序，將資料回存原來的陣列
  
  

  
             

         
         



• Radix Sort(LSD)圖解：
  
  
  

  
  

  

  




• 時間複雜度(Time Complexity)
  
  
  
  • Best Case：Ο(d × (n+r))
  
  
  • Worst Case：Ο(d × (n+r))
  
  
  • Average Case：Ο(d × (n+r))
  
  
  • 說明：
    
    
    
    • d = 執行回合數
    
    
    • n = 數列長度
    
    
    • r = 基數
    
    
    • 每回合將資料分配到桶子需Ο(n)
    
    
    • 每回合將桶子內的資料取出，合併成數列需Ο(r)
    
    
    • ∴每回合需Ο( n + r)
    
    

    
    

  
  
  
  

  
  



• 空間複雜度(Space Complexity)：Ο(n × r)
  
  
  
  • 使用二維陣列來當桶子：Ο(n × r)
    
    
    
    • n = 數列長度
    
    
    • r = 基數
    
    
    • 需要r個桶子，每個桶子需可放n筆資料  Ο( n × r)
    
    

    
    

  
  
  • 使用鏈結串列來當桶子：Ο(n)
    
    
    
    • n = 數列長度
    
    

    
    

  
  

  
  



• 穩定性(Stable/Unstable)：穩定(Stable)



• 演算法
  
  
         

  
             
  • JS(LSD)
             
             
         

  
             

  
  

  
  
  //初始化桶子
  
  var initArray = function(buckets, count){
  
      for(var i = 0; i < buckets.length; i++){
  
          buckets[i]  = new Array(buckets.length);
  
          count[i] = 0;
  
      }
  
  }
  
  
  
  var radixSort = function(data){
  
      var MAX = 100;                          // 數的上限
  
      var dataIndex = 0, radix = 1;           // radix = 1, 10, 100,...
  
      var buckets = new Array(data.length),   // 桶子 
  
          count = new Array(data.length);     // 記錄每個桶子裝了幾個數值
  
      initArray( buckets, count );            // 初始化桶子
  
  
  
      while(radix <= MAX){                    // 若基數沒有超出上限
  
      
  	
  // 分配
  
          for(var i = 0; i < data.length; i++){
  
              var LSD = parseInt((data[i]/radix)) % 10;    // 計算LSD(=那一個桶子)
  
              buckets[LSD][count[LSD]] = data[i];          // 將資料放到對應的桶子
  
              count[LSD]++;
  
          }
  
          radix *= 10;                                     // 更新基底：1->10, 10->100
  
  	
  	
  
  
          // 合併
  
          dataIndex = 0;
  
          for(var i = 0; i < data.length; i++){         // 將桶子內的資料合併
  
              if(count[i] != 0){                        // 如果桶子內有資料
  
                  for(var j =0 ; j < count[i]; j++){
  
                      data[dataIndex++] = buckets[i][j];
  
                  }
  
              }
  
              count[i] = 0;                             // 歸0，以便下一回合使用
  
          }
  	
  	
  
  
      }
  
  };
  
  
  
  radixSort(data);