JavaScript 实现基数排序

Question

简介

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O（n²）	√
快排、归并、希尔、堆	O（nlogn）	√
桶、计数、基数	O（n）	×

顾名思义，按照一个基本位，来对数据上的每一位进行排序。比如字符串 abcdefg ，可以对每一位采取计数排序或桶排序进行处理。

代码

function radixSort(arr) {
  const n = arr.length
  const m = getMax(arr)
  for (let exp = 1; Math.floor(m / exp) > 0; exp *= 10) {
    countingSort(arr, exp)
  }
}

function getMax(arr) {
  let max = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}

function countingSort(arr, exp) {
  const n = arr.length
  let output = new Array(n)
  let count = Array.from({length: 10}, _ => 0)
  for (let i = 0; i < n; i++) {
    count[Math.floor(arr[i] / exp) % 10]++
  }
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1]
  }
  for (let i = n - 1; i >= 0; i--) {
    output[count[Math.floor(arr[i] / exp) % 10] - 1] = arr[i]
    count[Math.floor(arr[i] / exp) % 10]--
  }
  for (let i = 0; i < n; i++) {
    arr[i] = output[i]
  }
}

const arr=[170, 45, 75, 90, 802, 24, 2, 66]
radixSort(arr) // [2, 24, 45, 66, 75, 90, 170, 802]

总结

1. 基数排序时间复杂度 O（n）
2. 对排序数据有要求，需要可以分割出独立的「位」来比较，而且位之间有递进的关系，如果 a 比 b 大，那么后面的位就不用比较了。