My Muri Life

切换主题

本页目录

基数排序 ​

基本思想：基数排序可以认为是计数排序的升级版，其根据数字的有效位或基数（这也是它为什么叫基数排序）将整数分布到桶中。比如，对于十进制数，使用的基数是10。

算法过程描述：

  1. 首先找出无序数组的取值范围为[min, max]，此时的偏移量为min；
  2. 初始化长为RADIX = 10统计数组cnts；
  3. 遍历原数组，统计每个数字num在(max - min) / signDigit位上的数idx = ~~(((num - min) / signDigit) % RADIX)出现的次数cnts[idx]++；
  4. 将统计数组转化为前缀和数组；
  5. 倒序遍历原数组（同计数排序，为了保证算法稳定），前缀和数组的每项表示：
    1. 当前位（个位、十位等）上值小于等于idx的数有cnts[idx]个， 即A[len]在原数组中相对位置（排序后）应位于下标idxA = cnts[idx] - 1。
  6. 每遍历完成一次就出桶（即A = [...ret]）；
  7. 直到所有位均完成排序时，整个排序完成。

LSD ​

JavaScript
const radixSort = A => {
  const [RADIX, LEN] = [10, A.length]
  // 注意这里的闭包
  const getDigitRadix = (num, signDigit) => {
    return ~~(((num - min) / signDigit) % RADIX)
  }
  // 找出min与max
  let [min, max] = [Infinity, -Infinity]
  for (const num of A) {
    max = num > max ? num : max
    min = num < min ? num : min
  }

  const ret = Array(LEN).fill(0)
  for (let signDigit = 1; (max - min) / signDigit > 0; signDigit *= RADIX) {
    const cnts = Array(RADIX).fill(0)
    // LSD 词频统计
    for (const num of A) {
      const idx = getDigitRadix(num, signDigit)
      cnts[idx]++
    }
    // 将词频统计数组转化为前缀和
    for (let i = 1; i < RADIX; i++) {
      cnts[i] += cnts[i - 1]
    }
    // 倒序遍历数组
    let len = LEN
    while (--len >= 0) {
      const idx = getDigitRadix(A[len], signDigit)
      ret[--cnts[idx]] = A[len]
    }
    A = [...ret]
  }
  return A
}

算法应用 ​

场景
  • 如何给英文单词排序（多关键字排序）？
JavaScript
const radixSortWord = A => {
  const [ASCII, LEN] = [128, A.length]
  const getCharCode = (str, idx) => {
    if (str.length <= idx) return 0
    return str.charCodeAt(idx)
  }
  // 找出min与max
  let [minLen, maxLen] = [Infinity, -Infinity]
  for (const str of A) {
    maxLen = str.length > maxLen ? str.length : maxLen
    minLen = str.length < minLen ? str.length : minLen
  }

  const ret = Array(LEN).fill(0)
  for (let i = (maxLen - minLen) - 1; i >= 0; i--) {
    const cnts = Array(ASCII).fill(0)
    // LSD 词频统计
    for (const str of A) {
      const idx = getCharCode(str, i)
      cnts[idx]++
    }
    // 将词频统计数组转化为前缀和
    for (let j = 1; j < ASCII; j++) {
      cnts[j] += cnts[j - 1]
    }
    // 倒序遍历数组
    let len = LEN
    while (--len >= 0) {
      const idx = getCharCode(A[len], i)
      ret[--cnts[idx]] = A[len]
    }
    A = [...ret]
  }
  return A
}
  • 如何将10万个手机号码从小到大排序，你有什么比较快速的排序方法呢 ？