计数排序 - 算法原理 - 计数排序的基本思想

计数排序 - 算法原理 - 计数排序的基本思想

引言

在计算机科学的浩瀚海洋中，排序算法犹如璀璨的明珠，各自散发着独特的光芒。常见的排序算法有冒泡排序、快速排序、归并排序等，而计数排序则是其中一颗别具特色的明珠。它不像其他一些排序算法基于元素之间的比较来确定顺序，而是利用了整数的特性，以一种高效且独特的方式完成排序任务。下面，我们就来深入探究计数排序的基本思想。

计数排序的基本思想概述

计数排序的核心思想是通过统计每个待排序元素出现的次数，进而确定每个元素在排序后数组中的位置。这种方法特别适用于整数排序，尤其是当待排序元素的取值范围相对较小时，其时间复杂度能达到线性级别，展现出卓越的性能。

为了更清晰地理解这一思想，我们可以将其类比为统计班级学生的考试成绩。假设班级里学生的考试成绩范围是 0 - 100 分，我们要对这些成绩进行排序。可以准备 101 个盒子（从 0 到 100 编号），然后依次将每个学生的成绩放入对应的盒子中，最后从 0 号盒子开始，依次取出每个盒子里的成绩，这样就得到了按成绩从小到大排序的结果。

计数排序的具体步骤

步骤一：找出待排序数组中的最大值和最小值

这一步是为了确定计数数组的长度。计数数组的长度应该等于最大值减去最小值再加 1。例如，待排序数组为 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]，其中最小值是 1，最大值是 9，那么计数数组的长度就是 9 - 1 + 1 = 9。

步骤二：统计每个元素出现的次数

创建一个计数数组，其长度在步骤一中已经确定。遍历待排序数组，对于每个元素，将计数数组中对应位置的值加 1。以上面的数组为例，计数数组初始值都为 0，遍历数组后，计数数组的状态如下：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| —- | —- | —- | —- | —- | —- | —- | —- | —- | —- |
| 值 | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 1 |
这里计数数组的索引表示待排序数组中的元素减去最小值后的结果，例如索引 0 对应元素 1（因为 1 - 1 = 0），索引 1 对应元素 2（因为 2 - 1 = 1），以此类推。

步骤三：对计数数组进行累加

从计数数组的第二个元素开始，将每个元素的值加上前一个元素的值。累加后的计数数组表示每个元素在排序后数组中的最后一个位置。继续上面的例子，累加后的计数数组如下：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| —- | —- | —- | —- | —- | —- | —- | —- | —- | —- |
| 值 | 0 | 2 | 3 | 5 | 6 | 9 | 10 | 10 | 11 |

步骤四：将元素放入排序后的数组

创建一个与待排序数组长度相同的结果数组。从后往前遍历待排序数组，对于每个元素，根据计数数组中对应位置的值确定其在结果数组中的位置，然后将该元素放入结果数组，并将计数数组中对应位置的值减 1。遍历完待排序数组后，结果数组就是排序好的数组。

代码实现（Python）

def counting_sort(arr):
    # 步骤一：找出最大值和最小值
    min_val = min(arr)
    max_val = max(arr)
    # 步骤二：统计每个元素出现的次数
    count_array = [0] * (max_val - min_val + 1)
    for num in arr:
        count_array[num - min_val] += 1
    # 步骤三：对计数数组进行累加
    for i in range(1, len(count_array)):
        count_array[i] += count_array[i - 1]
    # 步骤四：将元素放入排序后的数组
    result = [0] * len(arr)
    for num in reversed(arr):
        index = count_array[num - min_val] - 1
        result[index] = num
        count_array[num - min_val] -= 1
    return result
# 测试
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = counting_sort(arr)
print(sorted_arr)

复杂度分析

时间复杂度

计数排序的时间复杂度为 $O(n + k)$，其中 $n$ 是待排序数组的长度，$k$ 是待排序元素的取值范围。由于只需要遍历待排序数组和计数数组各一次，所以在 $k$ 相对较小时，计数排序的效率非常高。

空间复杂度

计数排序的空间复杂度为 $O(k)$，主要用于存储计数数组。因此，当 $k$ 很大时，计数排序需要的额外空间会比较多。

适用场景

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

1. 待排序元素为整数。
2. 待排序元素的取值范围相对较小。
3. 对排序速度有较高要求。

总结

计数排序以其独特的思想和高效的性能在排序算法中占据了一席之地。通过统计元素出现的次数，避免了元素之间的比较，从而在特定场景下能够快速完成排序任务。然而，它也有一定的局限性，即对元素的取值范围有一定要求。在实际应用中，我们需要根据具体情况选择合适的排序算法，以达到最佳的排序效果。

希望通过本文的介绍，你对计数排序的基本思想有了更深入的理解，能够在合适的场景中灵活运用这一算法。