Skip to main content

计数排序

计数排序 是一种基于键值的排序算法, 适用于元素范围较小的情况. 它不是通过比较元素来排序, 而是通过统计每个元素出现的次数, 然后根据这些计数来确定元素的最终位置. 计数排序特别适合排序整数或者是具有某种顺序关系的元素, 且适用于较小的元素范围.

工作原理​

  1. 找出数据范围: 首先确定待排序数据的最大值和最小值, 计算出数据范围.

  2. 统计频率: 创建一个计数数组, 记录每个元素出现的次数. 这个数组的下标对应元素的值, 值对应的是该元素出现的次数.

  3. 计算位置: 根据计数数组, 计算每个元素在最终排序数组中的位置. 这个位置可以通过累加计数数组中的值来确定.

  4. 填充排序结果: 根据计算出的位置信息, 填充最终排序数组.

适用情况​

  • 数据范围较小: 计数排序的效率依赖于数据范围. 当数据的最大值和最小值差距较大时, 计数排序的空间复杂度和时间复杂度都可能变得很高.
  • 整数或可离散化的数据: 计数排序通常用于排序整数, 或者是可以映射到整数的其他类型数据.

时间复杂度​

  • 时间复杂度: O(n + k), 其中 n 是输入数据的大小, k 是数据范围的大小(即最大值与最小值之间的差). 当数据范围 k 较小, 计数排序的效率就很高.
  • 空间复杂度: O(k), 需要一个计数数组来存储每个元素的出现次数.

示例代码​

function countingSort(arr) {
  // Step 1: Find the range of the elements
  let max = Math.max(...arr)
  let min = Math.min(...arr)

  // Step 2: Create a counting array
  let range = max - min + 1
  let count = new Array(range).fill(0)

  // Step 3: Count the frequency of each element
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++ // Count the frequency, offset by min value
  }

  // Step 4: Reconstruct the sorted array
  let sortedArr = []
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      sortedArr.push(i + min) // Rebuild sorted array
      count[i]--
    }
  }

  return sortedArr
}

优缺点​

优点:

  • 线性时间复杂度: 当数据范围 k 相对较小且数据量 n 较大的时候, 计数排序可以实现接近 O(n) 的时间复杂度.
  • 稳定排序: 计数排序是稳定的, 即相同元素的顺序不会被改变.

缺点:

  • 空间复杂度较高: 需要一个计数数组, 尤其是当数据的最大值很大时, 空间开销会很大.
  • 仅适用于整数或离散数据: 计数排序主要用于整数数据或可以离散化的数据, 不能直接应用于浮动类型或字符串类型等数据.
  • 受限于数据范围: 当数据范围较大时, 计数排序的空间复杂度和时间复杂度都会受到影响, 可能变得低效.

应用场景​

计数排序适用于数据量大且数据范围小的情况, 比如排序考试成绩(通常是 0-100 的整数)或者某些特殊的图像处理任务(比如对灰度值进行排序).