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

题目描述
给定一个包含 n 个元素的数组 arr，数组中的元素可能重复，且没有明确的范围限制（例如整数可能很大）。请使用比较计数排序（Comparison Counting Sort）算法对数组进行稳定排序。你需要实现算法的稳定版本，并进一步优化其空间复杂度，使得额外空间使用从 O(n) 降低到更优水平（理想情况下 O(k)，其中 k 为不同元素的数量），同时保持排序的稳定性。请详细解释每一步的原理，并分析时间与空间复杂度。

解题过程循序渐进讲解

1. 回顾基本比较计数排序
比较计数排序的核心思想是：对于每个元素，统计数组中比它小的元素个数，这个个数直接决定了该元素在有序数组中的目标位置。

• 基本步骤：
  1. 初始化一个计数数组 count[]，大小与输入数组相同，全为0。
  2. 对每个下标 i，遍历所有下标 j (j ≠ i)，如果 arr[j] < arr[i]，则 count[i]++。如果 arr[j] == arr[i] 且 j < i，则 count[i]++（这是为了在相等元素时保持原始相对顺序，即稳定性关键）。
  3. 根据 count[i] 的值，将 arr[i] 放到结果数组的 count[i] 位置。
• 缺点：
  • 需要 O(n²) 次比较，时间复杂度 O(n²)。
  • 需要额外 O(n) 空间存储 count[] 和结果数组。
  • 对相等元素的处理需特殊规则以保持稳定。

2. 稳定版本的实现要点
在步骤2的比较中，不仅要比较 <，还要在相等时考虑下标关系：

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. 空间复杂度优化进阶思路
基本方法需要 O(n) 空间存储 count[] 和结果数组。我们可以优化到 O(k)（k 为不同元素的数量），思路如下：

• 第一步：识别不同元素及其频率

  1. 使用一个字典（或哈希表）freq 记录每个不同元素出现的频率，同时按遍历顺序记录元素首次出现顺序（以维护稳定性）。
  2. 同时，用一个列表 unique 按遍历顺序存储不同元素。

• 第二步：计算每个不同元素的“目标起始位置”

  1. 对 unique 列表进行排序（可用普通排序算法，因为 k 通常远小于 n）。
  2. 但为了保持稳定性，我们不需要对 unique 排序，而是直接计算：
     对每个不同元素，统计比它小的不同元素的频率总和，即为该元素在结果中的起始位置。
  3. 具体做法：
     • 遍历 unique，对每个元素 u，计算 start[u] = sum(freq[v] for v in unique if v < u)。
     • 这可以通过先对 unique 排序（不影响稳定，因为相同元素已合并），然后累加频率得到。

• 第三步：将元素放到结果数组

  1. 初始化结果数组 result 大小为 n。
  2. 遍历原数组 arr，对于每个元素 arr[i]：
     • 从 start 中取得它的目标位置 pos = start[arr[i]]。
     • 将 arr[i] 放入 result[pos]。
     • 将 start[arr[i]] 增加 1（这样相同元素的下一个会放在下一个位置，保持顺序）。
  3. 最终 result 即为稳定排序结果。

4. 复杂度分析

• 时间复杂度：

  • 统计频率和构建 unique：O(n)。
  • 计算 start 位置：需要比较不同元素间大小，最坏 O(k²)（k 为不同元素数量）。若 k 远小于 n，这一步开销小。
  • 放置元素到结果数组：O(n)。
  • 总体：O(n + k²)。当 k 接近 n 时退化为 O(n²)，但此时与原始算法相同；当 k 很小（如有限范围整数）时接近 O(n)。

• 空间复杂度：

  • 字典 freq 和 start：O(k)。
  • 结果数组：O(n)（输出必需）。
  • 额外空间（不包括输出）：O(k)，优于原始 O(n)。

5. 举例说明
假设数组 arr = [4, 2, 2, 8, 3, 4]。
步骤：

1. 统计频率并记录顺序：
   freq = {4:2, 2:2, 8:1, 3:1}，unique = [4, 2, 8, 3]（按出现顺序）。
2. 对 unique 按值排序得 [2, 3, 4, 8]，计算累积频率得 start 位置：
   • 2: start=0
   • 3: start=2（因为2频率2）
   • 4: start=3（2频率2 + 3频率1）
   • 8: start=5（2+1+2）
3. 遍历原数组放置（用 start 当前位置，然后递增）：
   1. 4 → pos=3，result[3]=4，start[4]=4
   2. 2 → pos=0，result[0]=2，start[2]=1
   3. 2 → pos=1，result[1]=2，start[2]=2
   4. 8 → pos=5，result[5]=8，start[8]=6
   5. 3 → pos=2，result[2]=3，start[3]=3
   6. 4 → pos=4，result[4]=4，start[4]=5
      结果：[2, 2, 3, 4, 4, 8]，稳定（原数组中两个4和两个2的顺序保持不变）。

6. 进一步优化：避免 O(k²) 比较
若 k 较大，可对 unique 列表进行排序（O(k log k)）替代两两比较：

• 对 unique 排序后，遍历排序后的 unique，累加频率即可得到每个元素的起始位置。
• 此时时间复杂度为 O(n + k log k)，空间 O(k)（不包括输出）。

7. 总结
本题的进阶优化关键在于：

1. 利用频率统计合并相同元素，减少比较对象数量。
2. 通过起始位置映射和递增放置，自然保持稳定性。
3. 通过排序 unique 列表，将比较次数从 O(k²) 降到 O(k log k)，在 k 较小时更高效。
4. 最终算法在元素重复较多时（k << n）显著优于原始比较计数排序，且保持了稳定性，额外空间从 O(n) 降到 O(k)。