基數排序法(Radix Sort)，與前篇的桶排序都是非比較排序，也屬於「分配性」的排序方式，原理依據鍵值排序的方向又分為兩種:

• LSD(Least Significant Digit First)： 從最右邊的位數開始排序
• MSD(Most Significant Digit First)： 從最左邊的位數開始排序

排序流程(LSD為例):

1. 取得每個資料位數(最小開始)的值
2. 依該位數大小排序資料
3. 取得下一個位數進行比較，重複1~2步驟，直到所有位數都排序完為止

下面利用28 96 5 33 60 169 170 249 362 44 84 123由小到大排序(使用LSD為例)
從最右邊位數開始排序: 個位數 > 十位數 > 百位數
而若都是十進位的數，可以產生0~9的空陣列來進行分配排序

JavaScript

function radixSort(arr){

  //找出最大位數
  let maxDigits = 0
  for (let num of arr) {
    maxDigits = (maxDigits < num.toString().length) ? num.toString().length : maxDigits
  }

  for (let i = 0; i < maxDigits; i++) {
    //產生空桶子
    let buckets = Array.from({length:10}, () => [])
    //依據位數大小分類
    for (let j = 0; j < arr.length; j++) {
      let radix = Math.floor(arr[j] / Math.pow(10,i)) % 10 
      buckets[radix].push(arr[j])
    }
    //合併桶子的資料
    arr = [].concat(...buckets)
  }

  return arr
}

let arr = [28, 96, 5, 33, 60, 169, 170, 249, 362, 44, 84, 123]

console.log(radixSort(arr))
//[5, 28, 33, 44, 60, 84, 96, 123, 169, 170, 249, 362]

Python

#Radix Sort
def radixSort(arr):
    maxNum = max(arr)
    digits = 1
    while maxNum >= 10**digits:
        digits += 1
    for i in range(digits):
        #產生空桶子
        buckets = [[] for _ in range(10)]
        #依據位數大小分類
        for j in arr:
            radix = int(j/(10**i) % 10)
            buckets[radix].append(j)
        #合併桶子的資料
        x = 0
        for y in range(10):
            for num in buckets[y]:
                arr[x] = num
                x += 1
    return arr

data = [28, 96, 5, 33, 60, 169, 170, 249, 362, 44, 84, 123]

print(radixSort(data))
#[5, 28, 33, 44, 60, 84, 96, 123, 169, 170, 249, 362]