介绍

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

原理

将所有待比较数值（ 正整数 ）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

复杂度

• 最坏时间复杂度$O(kN)$
• 空间复杂度${\displaystyle O(k+N)}$

动画

实现

JavaScript

/*
* Radix sorts an integer array without comparing the integers.
* It groups the integers by their digits which share the same
* significant position.
* For more information see: https://en.wikipedia.org/wiki/Radix_sort
*/
function radixSort (items, RADIX) {
  // default radix is then because we usually count to base 10
  if (RADIX === undefined || RADIX < 1) {
    RADIX = 10
  }

  let maxLength = false
  let placement = 1

  while (!maxLength) {
    maxLength = true
    const buckets = []

    for (let i = 0; i < RADIX; i++) {
      buckets.push([])
    }

    for (let j = 0; j < items.length; j++) {
      const tmp = items[j] / placement
      buckets[Math.floor(tmp % RADIX)].push(items[j])
      if (maxLength && tmp > 0) {
        maxLength = false
      }
    }

    let a = 0
    for (let b = 0; b < RADIX; b++) {
      const buck = buckets[b]
      for (let k = 0; k < buck.length; k++) {
        items[a] = buck[k]
        a++
      }
    }
    placement *= RADIX
  }
  return items
}

参考

• 基数排序 - 维基百科，自由的百科全书 (opens new window)