排序算法之：比较计数排序（Comparison Counting Sort）的稳定版本实现与优化

题目描述
比较计数排序是一种非基于比较的排序算法，其核心思想是：对于待排序数组中的每个元素，统计比它小的元素个数，从而确定其在有序数组中的位置。题目要求实现一个稳定版本的比较计数排序，确保相等元素的相对顺序在排序后保持不变，并分析其时间复杂度和空间复杂度。

解题过程

步骤1：理解基本比较计数排序
基本比较计数排序的步骤如下：

1. 遍历数组，对于每个元素arr[i]，统计比它小的元素个数，存入计数数组count[i]。
2. 根据count[i]的值，将arr[i]放到结果数组的对应位置（索引为count[i]）。

但这种方法在遇到相等元素时无法保证稳定性，因为相等元素可能被任意排列。

步骤2：引入稳定性保证
为实现稳定性，需要调整计数策略：

1. 统计小于或等于每个元素arr[i]的元素个数，但需确保相等元素的顺序不变。
2. 优化方法：先统计比每个元素小的元素个数，再通过调整计数确定最终位置。

具体步骤：

• 初始化计数数组count，长度与输入数组相同，全部设为0。
• 第一轮遍历：对于每个索引i，统计比arr[i]小的元素个数：

  for i in range(n):
      for j in range(n):
          if arr[j] < arr[i]:
              count[i] += 1
  

• 此时count[i]表示比arr[i]小的元素个数，但相等元素会得到相同的计数值，导致位置冲突。

步骤3：处理相等元素
为保持稳定性，需确保相等元素按原始顺序排列：

1. 修改计数策略：对于相等元素，后出现的元素应获得更大的计数值。
2. 调整计数循环：当arr[j] == arr[i]且j < i时，count[i]也应增加1（即统计索引更小的相等元素）：

   for i in range(n):
       for j in range(n):
           if arr[j] < arr[i] or (arr[j] == arr[i] and j < i):
               count[i] += 1
   

3. 此时count[i]直接表示arr[i]在有序数组中的目标索引。

步骤4：构建有序数组

1. 创建空结果数组result，长度与输入相同。
2. 遍历原数组，将每个arr[i]放入result[count[i]]位置：

   result = [0] * n
   for i in range(n):
       result[count[i]] = arr[i]
   

步骤5：复杂度分析

• 时间复杂度：两层循环导致比较次数为O(n²)，适用于小规模数据。
• 空间复杂度：需要额外数组count和result，均为O(n)空间。

步骤6：优化方向

1. 减少比较次数：若元素范围已知，可结合计数排序（Counting Sort）优化，先将元素映射到频次数组，再计算前缀和以确定位置，将时间优化至O(n + k)（k为值域大小）。
2. 稳定性本质：通过统计“索引更小的相等元素”来维护顺序，此逻辑可扩展到自定义比较器。

总结
稳定版本的比较计数排序通过精细控制相等元素的计数规则，确保了排序的稳定性。虽然时间复杂度较高，但它是理解稳定性维护机制的经典案例，并为优化到线性时间排序（如基数排序的子过程）提供了基础。