一、计数排序和基数排序的基本原理
计数排序和基数排序都是非比较型的排序算法，它们通过巧妙的数学计算来达到排序目的。我们先来看看它们的基本工作原理。
计数排序的核心思想是统计每个元素出现的次数。比如我们要排序[1,4,1,2,3]这个数组：
- 先找到最大值4，创建计数数组count[0...4]
- 统计每个数字出现次数：count[1]=2，count[2]=1，count[3]=1，count[4]=1
- 根据计数数组重建排序后的数组：[1,1,2,3,4]
基数排序则是按位比较，从最低位到最高位依次排序。比如排序[170,45,75,90]：
- 先按个位数排序：[170,90,45,75]
- 再按十位数排序：[45,75,90,170]
- 最后按百位数排序（本例不需要调整）
二、两种排序的适用条件
计数排序最适合以下场景：
- 数据范围不大（最大值和最小值差值不大）
- 数据是整数（或者可以映射为整数）
- 数据重复较多时效率更高
基数排序的适用条件：
- 数据可以分割为独立的"位"
- 每位数据范围不大（适合使用计数排序作为子排序）
- 数据位数固定或可以补齐
举个实际例子，假设我们要排序100万个手机号码：
- 用计数排序不合适，因为数字范围太大（从10000000000到19999999999）
- 用基数排序就很合适，可以按位比较（每位数字0-9范围小）
三、处理非整数类型数据的技巧
当遇到非整数数据时，我们可以通过一些转换方法让它们适用于这两种排序算法。
浮点数处理： 可以将小数乘以10的n次方转为整数，排序后再转回小数。例如：
# 技术栈：Python nums = [3.14, 1.59, 2.65] # 原始浮点数数组 scale = 100 # 保留2位小数 int_nums = [int(x * scale) for x in nums] # [314, 159, 265] # 使用计数或基数排序处理int_nums # 排序后再转换回来 sorted_floats = [x/scale for x in sorted_ints]字符串处理： 字符串可以看作字符的序列，每个字符都有ASCII码值：
# 技术栈：Python words = ["apple", "banana", "cherry"] # 可以按字符的ASCII码值进行基数排序 # 先比较第1个字符，再比较第2个字符，依此类推自定义对象处理： 可以为对象设计一个整数键值映射函数：
# 技术栈：Python class Person: def __init__(self, name, age): self.name = name self.age = age people = [Person("Alice", 25), Person("Bob", 20)] # 按年龄排序，直接使用年龄作为整数键 ages = [p.age for p in people] # [25, 20]
四、实际应用示例
让我们看一个完整的例子，演示如何处理包含浮点数的数据：
# 技术栈：Python
def counting_sort_float(nums, decimal_places=2):
"""对浮点数进行计数排序"""
scale = 10 ** decimal_places
# 转换为整数
int_nums = [int(x * scale) for x in nums]
# 找到最小值和最大值
min_val = min(int_nums)
max_val = max(int_nums)
# 初始化计数数组
count = [0] * (max_val - min_val + 1)
# 统计每个整数出现的次数
for num in int_nums:
count[num - min_val] += 1
# 重建排序后的数组
sorted_ints = []
for i in range(len(count)):
sorted_ints.extend([i + min_val] * count[i])
# 转换回浮点数
sorted_floats = [x / scale for x in sorted_ints]
return sorted_floats
# 测试示例
nums = [3.14, 1.59, 2.65, 3.14, 1.59]
sorted_nums = counting_sort_float(nums)
print(sorted_nums) # 输出: [1.59, 1.59, 2.65, 3.14, 3.14]
五、技术优缺点分析
计数排序的优点：
- 时间复杂度O(n+k)，当k不大时非常高效
- 稳定排序，保持相同元素的相对位置
- 实现简单直观
计数排序的缺点：
- 需要额外空间存储计数数组
- 当数据范围很大时（k很大），效率下降
- 只能用于整数或可映射为整数的数据
基数排序的优点：
- 时间复杂度O(d(n+k))，对于位数d不大的数据很高效
- 可以处理更大范围的数据
- 稳定排序
基数排序的缺点：
- 需要稳定的子排序算法（通常用计数排序）
- 对于位数差异大的数据需要补齐
- 实现比计数排序复杂
六、使用注意事项
数据范围评估： 使用前先计算数据的最大值和最小值差，如果差值过大（比如超过100万），可能不适合计数排序。
内存考虑： 大数据范围会消耗大量内存，例如数据范围是0-10^9，计数数组就需要10^9的空间。
稳定性需求： 如果需要保持相同元素的原始顺序（如先按年龄排序，再按姓名排序），必须使用稳定排序。
数据类型转换： 浮点数转整数时要注意精度问题，避免舍入误差导致排序错误。
基数选择： 基数排序中基数的选择很重要，通常使用10（十进制位）或256（字节位）。
七、应用场景推荐
计数排序最适合：
- 学生成绩排序（0-100分）
- 年龄统计排序
- 小范围整数数据的快速排序
基数排序最适合：
- 手机号码排序
- 身份证号排序
- 大整数排序
- 固定长度的字符串排序
八、总结与建议
计数排序和基数排序在特定场景下性能优异，但它们都有各自的局限性。在实际应用中：
- 优先考虑数据特征：是否是整数？范围多大？位数是否固定？
- 小范围整数数据优先考虑计数排序
- 大范围但位数固定的数据考虑基数排序
- 非整数数据可以先转换为整数形式
- 注意内存消耗和精度问题
最后记住，没有最好的排序算法，只有最适合当前场景的排序算法。理解数据特征是选择排序方法的关键。
评论