计数排序
计数排序(Counting Sort)是一种非比较的排序算法,适用于对一定范围内的整数进行排序。它的核心思想是通过统计每个元素的出现次数,然后根据统计结果将元素放回正确的位置。计数排序的时间复杂度为 O(n + k),其中 n 是待排序数组的长度,k 是数组中元素的最大值。
计数排序的基本原理
计数排序的工作原理可以分为以下几个步骤:
- 统计元素出现次数:遍历数组,统计每个元素出现的次数,并存储在一个计数数组中。
- 累加计数数组:将计数数组中的每个元素累加,得到每个元素在排序后数组中的最终位置。
- 构建排序数组:根据计数数组中的信息,将原始数组中的元素放入正确的位置。
示例
假设我们有一个数组 [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]
。 - 进一步学习:了解其他非比较排序算法,如桶排序和基数排序。
备注
计数排序是学习排序算法的一个很好的起点,掌握它可以帮助你更好地理解其他更复杂的排序算法。