跳到主要内容

计数排序

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

计数排序的基本原理​

计数排序的工作原理可以分为以下几个步骤：

  1. 统计元素出现次数：遍历数组，统计每个元素出现的次数，并存储在一个计数数组中。
  2. 累加计数数组：将计数数组中的每个元素累加，得到每个元素在排序后数组中的最终位置。
  3. 构建排序数组：根据计数数组中的信息，将原始数组中的元素放入正确的位置。

示例​

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

步骤 1：统计元素出现次数​

首先，我们找到数组中的最大值，这里是 8。然后，我们创建一个长度为 9（最大值 + 1）的计数数组，并统计每个元素的出现次数。

plaintext
原始数组: [4, 2, 2, 8, 3, 3, 1]
计数数组: [0, 1, 2, 2, 1, 0, 0, 0, 1]

步骤 2：累加计数数组​

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

plaintext
累加后的计数数组: [0, 1, 3, 5, 6, 6, 6, 6, 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]
    
    # 构建排序数组
    sorted_arr = [0] * len(arr)
    for num in reversed(arr):
        sorted_arr[count[num] - 1] = num
        count[num] -= 1
    
    return sorted_arr

# 示例
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 是数组中元素的最大值。虽然计数排序在某些场景下非常有用，但它并不适用于所有情况，尤其是当数据范围较大时。

附加资源与练习​

  • 练习：尝试用计数排序对以下数组进行排序：[1, 4, 1, 2, 7, 5, 2]。
  • 进一步学习：了解其他非比较排序算法，如桶排序和基数排序。
备注

计数排序是学习排序算法的一个很好的起点，掌握它可以帮助你更好地理解其他更复杂的排序算法。