【Day29】[演算法]-基数排序法Radix Sort

基数排序法(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]