跳到主要内容

计数排序

计数排序（Counting Sort）是一种非比较型的排序算法，适用于对整数进行排序。它的核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 O(n + k)，其中 n 是待排序数组的长度，k 是数组中元素的最大值。

计数排序的基本原理​

计数排序的基本步骤如下：

  1. 统计频率：遍历数组，统计每个元素出现的次数，并存储在计数数组中。
  2. 计算前缀和：将计数数组中的值累加，得到每个元素在排序后数组中的最后一个位置。
  3. 放置元素：根据前缀和数组，将元素放置到正确的位置，并更新前缀和数组。

示例​

假设我们有一个数组 [4, 2, 2, 8, 3, 3, 1]，我们来看看计数排序是如何工作的。

步骤 1：统计频率​

首先，我们统计每个元素出现的次数。假设数组中的元素范围是 1 到 8，我们可以创建一个长度为 9 的计数数组（索引从 0 到 8）：

plaintext
计数数组：[0, 1, 2, 2, 1, 0, 0, 0, 1]

解释：

  • 元素 1 出现 1 次
  • 元素 2 出现 2 次
  • 元素 3 出现 2 次
  • 元素 4 出现 1 次
  • 元素 8 出现 1 次

步骤 2：计算前缀和​

接下来，我们将计数数组中的值累加，得到每个元素在排序后数组中的最后一个位置：

plaintext
前缀和数组：[0, 1, 3, 5, 6, 6, 6, 6, 7]

解释：

  • 元素 1 的最后一个位置是 1
  • 元素 2 的最后一个位置是 3
  • 元素 3 的最后一个位置是 5
  • 元素 4 的最后一个位置是 6
  • 元素 8 的最后一个位置是 7

步骤 3：放置元素​

最后，我们根据前缀和数组将元素放置到正确的位置，并更新前缀和数组：

plaintext
排序后的数组：[1, 2, 2, 3, 3, 4, 8]

代码实现​

以下是计数排序的 Python 实现：

python
def counting_sort(arr):
    # 找到数组中的最大值
    max_val = max(arr)
    
    # 初始化计数数组
    count = [0] * (max_val + 1)
    
    # 统计每个元素的出现次数
    for num in arr:
        count[num] += 1
    
    # 计算前缀和
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 创建输出数组
    output = [0] * len(arr)
    
    # 将元素放置到正确的位置
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    
    return output

# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)  # 输出: [1, 2, 2, 3, 3, 4, 8]

实际应用场景​

计数排序适用于以下场景：

  • 整数排序：计数排序特别适合对整数进行排序，尤其是当元素的范围不大时。
  • 小范围数据：当数据范围较小且数据量较大时，计数排序的效率非常高。
  • 稳定排序：计数排序是一种稳定排序算法，适用于需要保持相同元素相对顺序的场景。
提示

计数排序的时间复杂度为 O(n + k)，其中 n 是数组的长度，k 是数组中元素的最大值。当 k 远小于 n 时，计数排序的效率非常高。

总结​

计数排序是一种简单且高效的排序算法，特别适合对整数进行排序。它的核心思想是通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 O(n + k)，适用于元素范围较小的场景。

附加资源与练习​

  • 练习 1：尝试用计数排序对数组 [1, 4, 1, 2, 7, 5, 2] 进行排序，并验证结果。
  • 练习 2：修改计数排序的代码，使其能够处理包含负数的数组。
  • 进一步学习：了解其他非比较型排序算法，如基数排序和桶排序。

希望这篇教程能帮助你理解计数排序的基本原理和实现方法。继续练习和探索，你将掌握更多高效的排序算法！