My Muri Life

切换主题

本页目录

计数排序 ​

基本思想：计数排序是一种非常特殊的桶排序。找出待排序的数组中最大和最小的元素，统计数组中每个元素出现的次数，生成统计数组，遍历统计数组反向填充原数组。

算法过程描述：

  1. 首先找出无序数组的取值范围为[min, max]，此时的偏移量为min；
  2. 初始化长为max- min + 1统计数组cnts；
  3. 遍历原数组，统计每个元素出现的次数cnts[num - min]++；
  4. 遍历统计数组cnts，当遍历到的项值大于0时：
    1. 向原数组填充值i + min，下标步进idx++；
    2. 当前项的统计值递减cnts[i]--。
  5. 遍历完cnts时，完成排序。

不稳定版 ​

JavaScript
const countingSort = A => {
  if (A.length < 2) return A;
  let [min, max] = [Infinity, -Infinity]
  for (const num of A) {
    max = num > max ? num : max
    min = num < min ? num : min
  }
  const len = max - min + 1
  const cnts = Array(len).fill(0)
  // 统计对应元素个数
  for (const num of A) {
    cnts[num - min]++  // 偏移量为 min
  }
  for (let i = 0, idx = 0; i < len; i++) {
    while (cnts[i]-- > 0) {
      A[idx++] = i + min  // 偏移量为 min
    }
  }
}

稳定版 ​

算法过程描述：

  • 前缀和数组的每项表示（倒序遍历原数组len = A.length-1，len递减）：
    • 无min偏移时：原数组A中，小于等于A[len]的元素有cnts[A[len]]个，即：A[len]在原数组中相对位置（排序后）应位于下标idx = cnts[A[len]] - 1（此处-1是因为数组从下标0开始）；
    • 有min偏移时：原数组A中，小于等于A[len]的元素有cnts[A[len] - min]个，即：A[len]在原数组中相对位置（排序后）应位于下标idx = cnts[A[len] - min] - 1。
  • 这里倒序遍历是为了保证算法稳定性：简单来说就是模拟元素的出桶入桶顺序，倒序遍历保证了先入桶的元素先出桶（即队列）。
JavaScript
const countingSort = A => {
  let len = A.length
  if (len < 2) return A;
  let [min, max] = [Infinity, -Infinity]
  for (const num of A) {
    max = num > max ? num : max
    min = num < min ? num : min
  }
  const cntLen = max - min + 1
  const cnts = Array(cntLen).fill(0)
  // 统计对应元素个数
  for (const num of A) {
    cnts[num - min]++  // 偏移量为 min
  }
  // 计算统计数组前缀和
  for (let i = 1; i < cntLen; i++) {
    cnts[i] += cnts[i - 1]
  }
  // 倒序遍历原数组，从统计数组中找到位置，填入结果数组
  const ret = Array(len).fill(0)
  while (--len >= 0) {
    ret[--cnts[A[len] - min]] = A[len]
  }
  return ret
}

算法应用 ​

场景