计数排序（Counting Sort）的进阶应用：对非整数类型数据（如字符和自定义对象）的排序

题目描述

我们已熟知计数排序可以对整数数组（包括负数）进行高效排序。现在，我们将其推广到更广泛的数据类型：

1. 字符数组排序：对由小写字母组成的字符串或字符数组按字典序排序
2. 自定义对象排序：对具有离散键值的对象集合按特定键排序

关键挑战在于：如何将非整数类型映射到计数数组的索引，同时保持排序的稳定性。

解题思路详解

步骤1：理解核心原理扩展

计数排序的核心是：

1. 确定数据范围
2. 统计每个值出现的次数
3. 计算累积计数（前缀和）
4. 根据累积计数将元素放到正确位置

对于非整数类型，我们需要一个映射函数将其键值转换为整数索引。

步骤2：字符数组排序的实现

子步骤2.1：问题建模

假设我们有字符数组：['d', 'a', 'c', 'b', 'a', 'd']

字符在内存中实际上以ASCII码存储：

• 'a' = 97
• 'b' = 98
• 'c' = 99
• 'd' = 100

我们可以直接使用字符的ASCII码作为键值。

子步骤2.2：实现细节

def counting_sort_chars(arr):
    """
    对字符数组进行计数排序
    """
    if not arr:
        return arr
    
    # 步骤1：确定字符范围
    # 假设只包含小写字母，ASCII码范围是97-122
    min_char = min(arr)
    max_char = max(arr)
    
    # 计算偏移量，使最小字符对应索引0
    offset = ord(min_char)  # 获取字符的ASCII码
    
    # 步骤2：创建计数数组
    # 范围大小 = 最大ASCII - 最小ASCII + 1
    range_size = ord(max_char) - offset + 1
    count = [0] * range_size
    
    # 步骤3：统计每个字符出现次数
    for char in arr:
        index = ord(char) - offset
        count[index] += 1
    
    # 步骤4：计算累积计数（前缀和）
    # count[i]现在表示小于等于字符i的元素个数
    for i in range(1, range_size):
        count[i] += count[i-1]
    
    # 步骤5：从后向前遍历原数组，将元素放到正确位置
    # 从后向前是为了保持稳定性
    output = [''] * len(arr)
    for i in range(len(arr)-1, -1, -1):
        char = arr[i]
        index = ord(char) - offset
        # count[index]-1是当前字符应该放置的位置
        output[count[index]-1] = char
        count[index] -= 1
    
    return output

子步骤2.3：示例演算

以['d', 'a', 'c', 'b', 'a', 'd']为例：

1. min_char='a'(97), max_char='d'(100), offset=97
2. 范围大小=100-97+1=4，计数数组初始为[0,0,0,0]
3. 统计：
   • 'd'(100)→索引3→count[3]=2
   • 'a'(97)→索引0→count[0]=2
   • 'c'(99)→索引2→count[2]=1
   • 'b'(98)→索引1→count[1]=1
   • 最终count=[2,1,1,2]
4. 累积计数：count=[2,3,4,6]
5. 从后向前放置：
   • 最后一个'd'(位置5)→索引3→count[3]=6→输出位置5→count[3]变为5
   • 倒数第二个'a'(位置4)→索引0→count[0]=2→输出位置1→count[0]变为1
   • 继续直到所有元素放置完成
   • 最终结果：['a','a','b','c','d','d']

步骤3：自定义对象排序的实现

子步骤3.1：问题建模

假设我们有一个学生类：

class Student:
    def __init__(self, name, grade):
        self.name = name
        self.grade = grade  # 成绩等级：'A', 'B', 'C', 'D', 'F'
    
    def __repr__(self):
        return f"{self.name}({self.grade})"

我们要按成绩等级排序，等级顺序为：'A' < 'B' < 'C' < 'D' < 'F'

子步骤3.2：实现细节

def counting_sort_objects(arr, key_func):
    """
    对自定义对象数组进行计数排序
    
    Args:
        arr: 待排序的对象数组
        key_func: 函数，输入对象，返回排序键值
    """
    if not arr:
        return arr
    
    # 步骤1：确定键值范围
    # 首先提取所有键值
    keys = [key_func(obj) for obj in arr]
    
    # 创建键值到索引的映射
    unique_keys = sorted(set(keys))
    key_to_index = {key: i for i, key in enumerate(unique_keys)}
    
    # 步骤2：创建计数数组
    count = [0] * len(unique_keys)
    
    # 步骤3：统计每个键值出现次数
    for key in keys:
        index = key_to_index[key]
        count[index] += 1
    
    # 步骤4：计算累积计数
    for i in range(1, len(count)):
        count[i] += count[i-1]
    
    # 步骤5：从后向前放置元素
    output = [None] * len(arr)
    for i in range(len(arr)-1, -1, -1):
        obj = arr[i]
        key = key_func(obj)
        index = key_to_index[key]
        
        # 放置到正确位置
        output[count[index]-1] = obj
        count[index] -= 1
    
    return output

子步骤3.3：具体应用

# 示例数据
students = [
    Student("Alice", 'B'),
    Student("Bob", 'A'),
    Student("Charlie", 'C'),
    Student("David", 'B'),
    Student("Eve", 'A'),
    Student("Frank", 'D')
]

# 按成绩排序
def get_grade(student):
    return student.grade

# 等级映射（可选，用于自定义排序顺序）
grade_order = {'A': 0, 'B': 1, 'C': 2, 'D': 3, 'F': 4}

def get_grade_index(student):
    return grade_order[student.grade]

# 使用方法1：直接使用字符键值
sorted_students = counting_sort_objects(students, get_grade)
print("按成绩排序（字符键值）:", sorted_students)
# 输出: [Bob(A), Eve(A), Alice(B), David(B), Charlie(C), Frank(D)]

# 使用方法2：使用映射后的整数键值（更可控的顺序）
sorted_students2 = counting_sort_objects(students, get_grade_index)
print("按成绩排序（映射键值）:", sorted_students2)
# 输出相同结果

步骤4：处理更复杂的情况

子步骤4.1：多键排序（稳定排序的链式应用）

如果要先按成绩排序，成绩相同再按姓名排序：

def multi_key_sort(arr, key_funcs):
    """
    多键排序：使用链式计数排序
    
    Args:
        arr: 待排序数组
        key_funcs: 键值函数列表，按优先级从低到高排列
    """
    # 从最低优先级键开始排序
    result = arr[:]
    
    # 按优先级从低到高依次排序（稳定排序保证高级别键排序不会被低级别破坏）
    for key_func in reversed(key_funcs):
        result = counting_sort_objects(result, key_func)
    
    return result

# 示例：先按成绩，成绩相同按姓名首字母
students2 = [
    Student("Alice", 'B'),
    Student("Bob", 'A'),
    Student("Charlie", 'B'),  # 与Alice成绩相同
    Student("David", 'B'),    # 与Alice成绩相同
    Student("Eve", 'A')
]

def get_first_letter(student):
    return student.name[0]

sorted_multi = multi_key_sort(students2, [get_first_letter, get_grade])
print("多键排序结果:", sorted_multi)
# 输出: [Bob(A), Eve(A), Alice(B), Charlie(B), David(B)]

子步骤4.2：处理大范围稀疏键值

当键值范围很大但实际值很稀疏时，可以使用字典代替数组：

def sparse_counting_sort(arr, key_func):
    """
    适用于稀疏键值的计数排序
    """
    if not arr:
        return arr
    
    # 使用字典存储计数
    count_dict = {}
    
    # 统计每个键值出现次数
    for obj in arr:
        key = key_func(obj)
        count_dict[key] = count_dict.get(key, 0) + 1
    
    # 获取排序后的键值列表
    sorted_keys = sorted(count_dict.keys())
    
    # 计算累积计数（使用字典）
    cumulative = {}
    total = 0
    for key in sorted_keys:
        cumulative[key] = total
        total += count_dict[key]
    
    # 分配输出数组
    output = [None] * len(arr)
    
    # 稳定放置元素
    for obj in arr:
        key = key_func(obj)
        output[cumulative[key]] = obj
        cumulative[key] += 1
    
    return output

步骤5：时间复杂度和空间复杂度分析

时间复杂度

• 字符排序：O(n + k)，其中k是字符范围大小（如小写字母为26）
• 对象排序：O(n + m)，其中m是唯一键值数量
• 多键排序：O(p × (n + m))，p是键值数量

空间复杂度

• 计数数组/字典：O(k)或O(m)
• 输出数组：O(n)
• 总计：O(n + k)或O(n + m)

步骤6：应用场景与限制

适用场景

1. 字符排序：DNA序列排序、文本处理
2. 离散键值对象：学生按年级排序、产品按类别排序
3. 稳定排序需求：需要保持相同键值的原始相对顺序
4. 小范围键值：键值范围远小于数据量时效率极高

限制与注意事项

1. 键值必须可比较且可映射：需要明确的顺序关系
2. 内存消耗：键值范围过大时内存消耗显著
3. 非比较排序：不适用于需要复杂比较逻辑的情况
4. 稳定性维护：必须从后向前遍历原数组才能保持稳定性

总结提升

计数排序对非整数类型的扩展展示了算法的通用性思维：

1. 映射思想：将复杂类型映射到简单整数域
2. 稳定性保持：通过从后向前遍历维持相对顺序
3. 多级排序：利用稳定性实现链式多键排序

这种思想在数据库索引、文件系统排序、大数据处理中都有广泛应用，是理解更复杂排序算法（如基数排序）的重要基础。