基數排序法是一種只針對整數的排序法，主要是使用一個整數的(個/十/百/千)位數大小去判斷哪個整數比較大，而非直接比較兩個數的大小去做排序。

排序的過程用圖解和動畫一定比較好理解，所以可以參考這個網站的 Radix Sort 圖解和動畫，以下也會用圖解來說明 :

Step1.

首先我們會有一個未排序的陣列，一個用來記數的陣列，一個用來儲存排序過的陣列。

Step2.

接下來有兩種可以排序的方式，分別是 :

• Least significant digit (LSD)：從最小位數排到最大
• Most significant digit (MSD)：從最大位數排到最小

這裡我們從個位數開始排起，例如第一個元素值的個位數是 6，那就將 6 放進 count array 索引 6 的位置，第二個元素值 45 因為個位數是 5，所以放到 count array 索引 5 的位置，以此類推。

所有元素都加入到 count array 後，其各索引的數字個數如下所示:

Step3.

再將放置在 count array 的元素重新組成陣列，放在 auxilliary array 內。

Step4.

再下一次排序時，取得是十位數的數字並把它們加入到 count array，然後一樣重新重組陣列，放在 auxilliary array，接著檢查是否還有百位數，沒有的話即完成排序。

撰寫基數排序法程式

了解基數排序法是怎麼排序後，我們來看看要怎麼寫這個排序法，根據上面的圖解分析，我們要知道 :

1. 要能取出一個數字的第 i 個位數的值
2. 要知道要排序到第幾位數，所以需要計算一個數字有幾位數
3. 然後還需要找出最大位數的那個數字

有以上幾點之後，我們才能去寫基數排序法，以下就一一撰寫需求對應的函式吧!

1. 要能取出一個數字的第 i 個位數的值

/**
 * 用來取得一個數字 num 的第 i 個位數的值，例如 getDigit(12345, 1) 會取出 4
 * @param {number} num - 被取出位數值的數字
 * @param {number} i - 取出第幾位，從個位數開始算
 */
function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

2. 要知道要排序到第幾位數，所以需要計算一個數字有幾位數

/**
 * 計算一個數字 num 為幾位數
 * @param {number} num - 被計算幾位數的數字
 */
function digitCount(num) {
  if(num === 0) return 1;
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

3. 還需要找出最大位數的那個數字

/**
 * 找出多個數字中的最大位數
 * @param {number} nums - 包含多個數字的陣列
 */
function mostDigits(nums) {
  let maxDigits = 0;
  for(let i = 0; i < nums.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
  }
  return maxDigits;
}

4. 最後完成執行 radix Sort 的函式

/**
 * 執行 radix Sort 的函式
 * @param {number} nums - 包含多個數字的陣列
 */
function radixSort(nums) {
  let maxDigitCount = mostDigits(nums);
  for (let k = 0; k < maxDigitCount; k++) {
    let digitBuckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < nums.length; i++) {
      let digit = getDigit(nums[i], k);

      // 想像有 10 個籠子，0~9，依據取到的該位數值將當前遍歷的數字放進去籠子裡面
      // 例如當前取個位數，digitBickets[2] 會出現 12
      digitBuckets[digit].push(nums[i]);
    }
    nums = [].concat(...digitBuckets);
  }
  return nums;
}

radixSort([23, 345, 5467, 12, 2345, 9852]);

時間/空間複雜度

完成程式後，來看看時間 & 空間複雜度。

• 時間複雜度: 最好、平均、最差都是 O(n * k)，從 radixSort 函式內的迴圈可以得知
• 空間複雜度: O(n+k)，存 n 個數字到 count array，k 次位數的比對所以會建立 k 次的 count array

n 為要排序的數字總數
k 為數字位數最多的數字的位數

參考資料

排序動畫