排序算法之：比较计数排序（Comparison Counting Sort）的进阶应用：稳定排序与空间优化

题目描述：给定一个包含n个元素的数组，每个元素可能包含多个属性（如姓名和分数）。要求使用比较计数排序实现稳定的多属性排序：先按分数降序排序，分数相同的按姓名字典序升序排序。同时优化算法空间复杂度，使其不超过O(n)。

解题过程：

1. 理解比较计数排序基本原理

   • 标准比较计数排序通过统计每个元素小于其他元素的个数来确定其最终位置
   • 对于每个元素arr[i]，计算count[i] = 小于arr[i]的元素数量
   • 然后根据count[i]将元素放置到正确位置

2. 处理多属性排序的比较逻辑

   def compare(a, b):
       # 先比较分数（降序）
       if a.score != b.score:
           return a.score > b.score  # 分数高的排前面
       # 分数相同比较姓名（升序）
       return a.name < b.name
   

3. 实现基础比较计数排序

   def comparison_counting_sort(arr):
       n = len(arr)
       count = [0] * n  # 记录每个元素应该排在第几位
   
       # 比较所有元素对
       for i in range(n):
           for j in range(i+1, n):
               if compare(arr[i], arr[j]):
                   count[i] += 1  # i应该在j前面
               else:
                   count[j] += 1  # j应该在i前面
   
       # 根据count数组构建结果
       result = [None] * n
       for i in range(n):
           result[count[i]] = arr[i]
   
       return result
   

4. 处理相等元素的稳定性问题

   • 当两个元素相等时，需要保持它们原有的相对顺序
   • 修改比较逻辑：当元素相等时，比较原始索引

   def stable_compare(a, b, idx_a, idx_b):
       if a.score != b.score:
           return a.score > b.score
       if a.name != b.name:
           return a.name < b.name
       # 完全相等时，保持原始顺序（索引小的在前）
       return idx_a < idx_b
   

5. 空间优化：原地重排

   • 标准方法需要O(n)额外空间存储结果
   • 使用循环重排技术实现原地排序：

   def in_place_comparison_sort(arr):
       n = len(arr)
       count = [0] * n
   
       # 计算count数组（同前）
       for i in range(n):
           for j in range(i+1, n):
               if compare(arr[i], arr[j]):
                   count[i] += 1
               else:
                   count[j] += 1
   
       # 原地重排
       for i in range(n):
           while count[i] != i:  # 当前位置不是正确位置
               # 交换到正确位置
               correct_pos = count[i]
               arr[i], arr[correct_pos] = arr[correct_pos], arr[i]
               count[i], count[correct_pos] = count[correct_pos], count[i]
   
       return arr
   

6. 时间复杂度与空间复杂度分析

   • 时间复杂度：O(n²) - 需要比较所有元素对
   • 空间复杂度：O(n) - 仅需count数组，原地重排版本无需额外结果数组
   • 稳定性：通过正确处理相等元素保证稳定性

7. 实际应用场景

   • 适合小规模数据或元素比较代价高的情况
   • 当排序稳定性很重要且数据规模较小时
   • 作为理解排序算法基本原理的教学示例

这个算法展示了如何通过简单的比较计数思想实现复杂的多属性排序，同时通过优化技术控制空间复杂度。