---
tags: DSA in JavaScript
---
# Ch.17 Radix Sort
從 bubble sort 介紹到 quick sort ，這些排序法都有幾個共通點：

1. 一定會比大小
2. 時間複雜度在 $O(nlog{_2}n)$ 以上

> 那有沒有辦法將時間複雜度再壓得更低一點呢？

有些只適用於特定條件的排序法可以解決這個煩惱，例如這篇分享的 radix sort。
Radix sort 是利用數字的特性發展出來的排序法，大概有這些步驟：

1. 準備一個代表 0 ~ 9 的空間
2. 將每個元素依照它們的第 $n$ 位數，放進這些空間裡
3. 由 0 到 9，依序將這些元素從空間裡拿出來
4. $n = n + 1$，回到步驟 2，直到 $n$ 超過最大元素的位數 (例：最大是 12432 五位數，則迴圈重複 5 次)

大概可以整理出 radix sort 幾個特性：

- 只適用於 10 進位的整數陣列
- 沒有互相比大小的動作，使用數字進位的特性來排序
- 不一定會比之前的排序法更快

一樣先看 helper function

// 找出元素 num 的第 place 位數字
const getDigit = (num, place) => {
  return ~~(Math.abs(num) / (Math.pow(10, place))) % 10
}

// 找出 num 是幾位數
const digitCount = num => {
  if (num === 0) return 1
  return ~~(Math.log10(Math.abs(num))) + 1
}

// 找出 nums 中，最大的數是幾位數
const mostDigits = nums => {
  let result = 1

  for (let i = 0; i < nums.length; i++) {
    result = Math.max(result, digitCount(nums[i]))
  }

  return result
}

大概都是找幾位數的問題，接著來到 sort 本體

const radixSort = nums => {
  const maxDigit = mostDigits(nums)
  // mostDigits 會決定迴圈的執行次數
  for (let k = 0; k < maxDigit; k++) {
    //準備一個 0 ~ 9 的空間
    let digitBuckets = Array.from({ length: 10 }, () => [])
    for (let i = 0; i < nums.length; i++) {
    // 取得 num[i] 的第 k 位數字之後，將元素放進相對應的空間內
      const digit = getDigit(nums[i], k)
      digitBuckets[digit].push(nums[i])
    }
    // 將空間內的元素再放回 nums，此時排序已經改變
    nums = [].concat(...digitBuckets)
  }
  return nums
}

接觸到 radix sort 時，又是一個開腦洞的過程，沒想到還可以這樣玩排序。而這樣的時間複雜度則是 $O(nk)$ n 代表陣列長度，k 則代表陣列中 mostDigits 的大小，空間複雜度則是 $O(n+k)$，因為考量到 mostDigits 大小，radix sort 在排列位數比較小的大量資料時會比其他排序法有利，像是排列某地區居民的年齡，但是在處理最大值大得誇張的資料，反而會因為位數太大而拖累速度，因此謹慎使用。