[小撒学算法]基数排序

小撒是一只好学的小鸭子，这天，小撒在学习算法

基数排序（Radix Sort）

如前所述，计数排序带来了空间成本太大的问题。为了解决这一问题，我们将在其基础上演变出新的算法：基数排序。

为了使得计数数组只开辟固定有限的空间，我们可以按位对元素进行排序。为了方便，我们以十进制为例，排序数组[329,657,457,839,436,720,355]：

基数排序示例

正确的做法是从低位开始向高位对元素进行排序，排序先使用元素的个位，然后是十位、百位...

而计数排序稳定排序的特性是这种算法得以正确运行的关键之一，使得基数排序在高位排序过程中保持了低位顺序的正确性，例如在个位排序时15在19之前，那么在十位排序时两者十位都是1的情况下两者将保持个位的顺序。

当然对于计算机体系而言，以2为底的幂次作为基数将使得排序更快，因为我们可以用更高效的位操作来获取每一位的值。我们以8进制为：

获得十进制数113的8进制表示的第2位

代码示例（js）

const countingSort = (arr, i) => {
  const counters = Array(10).fill(0)

  arr.forEach((item) => {
    counters[item[i]]++
  })

  counters.forEach((item, index) => {
    if (index !== 0) {
      counters[index] += counters[index - 1]
    }
  })

  const rtn = Array(arr.length)

  for (let j = arr.length - 1; j >= 0; j--) {
    const item = arr[j]
    const pos = counters[item[i]] - 1
    rtn[pos] = item
    counters[item[i]] = pos
  }

  return rtn
}

const sort = (arr) => {
  const max = getMax(arr)

  const digits = Math.floor(Math.log10(max)) + 1

  let map = arr.map((x) => {
    const v = Array(digits).fill(0).map((_, i) => {
      return Math.floor(x / Math.pow(10, i)) % 10
    })
    v.push(x)
    return v
  })

  let i = 0

  while (i < digits) {
    map = countingSort(map, i)
    i++
  }

  return map.map(item => item[digits])
}

小结

基数排序在计数排序的基础上，延续了线性时间的时间成本，同时将空间成本化为常量，是一种优秀的排序算法。