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

题目描述
给定一个包含 n 个元素的数组 arr，其中每个元素都是一个可比较的对象（例如整数、字符串或自定义结构）。请实现一个稳定的比较计数排序算法，对数组进行升序排序。算法应满足以下要求：

1. 使用基于比较的“计数”思想：对于每个元素，统计数组中比它小的元素个数，从而直接确定其排序后的位置。
2. 必须保证排序的稳定性，即相等元素的相对顺序在排序后保持不变。
3. 在保证稳定性的基础上，尝试对算法进行优化，减少不必要的比较或空间占用，并分析优化前后的时间复杂度和空间复杂度。

解题过程

第一步：理解比较计数排序的基本思想
比较计数排序是一种非比较类排序算法（虽然名叫“比较计数”，但实际上它通过计数来确定位置，而非直接交换比较）。其核心思想是：

• 对于数组中的每个元素 arr[i]，统计数组中严格小于 arr[i] 的元素个数，记为 count。
• 那么 arr[i] 在排序后数组中的正确索引就是 count（因为比它小的元素有 count 个，它应该放在第 count 位，索引从0开始）。
• 如果存在重复元素，则需特殊处理以保证稳定性。

基本版本（不稳定）的步骤：

1. 初始化一个计数数组 counts，长度与输入数组相同，用于存储每个元素对应的“小于它的元素个数”。
2. 对于每个 i（0 ≤ i < n），遍历所有 j（0 ≤ j < n），如果 arr[j] < arr[i]，则 counts[i]++。
3. 根据 counts 数组，将每个 arr[i] 放到输出数组的正确位置：output[counts[i]] = arr[i]。
4. 但这种方式在遇到重复元素时不稳定，因为相等元素不会计入 counts，导致它们可能被任意顺序放置。

第二步：实现稳定版本
为了保证稳定性，我们需要调整计数规则：

• 对于每个元素 arr[i]，统计小于或等于 arr[i] 的元素个数，但统计“小于或等于”时，如果遇到相等的元素，只统计在它前面的那些（即下标 j ≤ i 且 arr[j] == arr[i]），从而区分相同元素的顺序。
• 更常用的稳定做法是：先统计“小于”的个数，再通过累计处理确定位置。以下是详细步骤：

1. 初始化计数数组 count，长度为 n，全部设为 0。
2. 对于每一对索引 (i, j) 且 i ≠ j：
   • 如果 arr[i] > arr[j]，则 count[i]++（统计比 arr[i] 小的元素）。
   • 注意：这里不统计相等情况，以保证稳定性。
3. 此时 count[i] 表示严格小于 arr[i] 的元素个数，即 arr[i] 在有序数组中的最小可能索引。
4. 但由于存在重复元素，多个相同元素会有相同的 count 值，会冲突。因此，我们需要调整相同元素的位置：
   • 创建一个输出数组 output，大小与输入相同。
   • 对于每个 arr[i]，将其放入 output[count[i]]，但如果有多个相同元素，则按顺序放置：
     • 遍历原数组顺序，对于每个 arr[i]，在输出数组中找到位置 pos = count[i]，然后检查 output[pos] 是否已被占用。
     • 实际上，更简单的方法是：维护一个“位置指针”数组或直接累加调整。
5. 更高效的稳定实现（一次遍历放置）：
   • 步骤：
     a. 计算 count 数组（统计小于每个元素的个数）。
     b. 创建输出数组 output。
     c. 遍历原数组从后向前（为了保持稳定性）：
     • 对于当前元素 arr[i]，其排序后索引应为 count[i]。
     • 但相同元素需按逆序放置，从后向前遍历可保证原序中靠后的元素在输出中也靠后（因为我们会依次占用位置）。
     • 将 arr[i] 放入 output[count[i]]，然后将 count[i]++（这样下一个相同元素会放在当前位置之后，保持稳定）。
   • 示例：
     输入 arr = [4, 2, 2, 8]
     统计小于每个元素的个数：对于4，小于4的有{2,2}→count=2；对于第一个2，小于2的没有→count=0；对于第二个2，小于2的没有→count=0；对于8，小于8的有{4,2,2}→count=3。
     count = [2, 0, 0, 3]。
     从后向前遍历：
     i=3, arr[3]=8, pos=count[3]=3 → output[3]=8, count[3]++变为4。
     i=2, arr[2]=2, pos=count[2]=0 → output[0]=2, count[2]++变为1。
     i=1, arr[1]=2, pos=count[1]=0 → output[0]已被占用？不，此时 count[1] 是0，但注意：因为上一步 count[2] 变为1，而 count[1] 还是0，所以 output[0] 是空的，放入2，然后将 count[1]++变为1。
     i=0, arr[0]=4, pos=count[0]=2 → output[2]=4, count[0]++变为3。
     output = [2, 2, 4, 8]（稳定，两个2的顺序不变）。

第三步：优化
基本稳定版本需要进行 O(n²) 次比较（对每个 i，遍历所有 j），效率较低。我们可以从两个方向优化：

1. 优化1：减少比较次数

   • 注意到在统计“小于”个数时，对每个元素 i，我们都需要与所有其他元素比较。我们可以利用排序后的索引信息来减少重复比较吗？
   • 一种思路：先对数组进行排序（例如用 O(n log n) 排序），然后利用有序序列的特性快速计算“小于”计数，但这会改变原算法性质。
   • 更实际的优化：使用平衡二叉搜索树（BST）或 Fenwick 树来优化计数过程。具体方法：
     • 从后向前遍历原数组，将元素插入到数据结构中，并查询“小于当前元素的个数”。
     • 例如使用 Fenwick 树（树状数组）处理离散化后的值：先将数组去重排序得到值域，然后遍历原数组时，查询小于当前值的元素个数（即前缀和），然后将当前值的计数+1。
     • 这样时间复杂度可降为 O(n log m)，其中 m 是值域大小。但需要额外 O(m) 空间，且要求元素可离散化。

2. 优化2：空间优化

   • 基本版本需要 O(n) 的 count 数组和 O(n) 的输出数组，共 O(n) 额外空间。
   • 可以尝试原地排序吗？比较计数排序本质上依赖计数来确定位置，难以严格原地，但我们可以尝试减少一个数组：在计算 count 后，直接在原数组上通过交换来放置元素，但交换过程容易破坏稳定性，需要谨慎处理。
   • 一种“伪原地”方法：将 output 数组复用为原数组，但需要额外 O(n) 空间暂存被覆盖的元素，实际空间复杂度仍为 O(n)。

3. 优化3：针对整数或小范围数据的优化

   • 如果元素是整数且范围不大，可直接使用计数排序（非比较计数），用频率数组统计每个值的出现次数，然后累加得到“小于或等于”的计数，再稳定放置。这是 O(n + k) 时间（k 是值域范围），且稳定。

第四步：复杂度分析

• 基本稳定版本：
  • 时间：需要两两比较，O(n²) 次比较和 O(n) 次赋值。
  • 空间：O(n) 用于 count 数组和 output 数组。
• 优化版本（使用 Fenwick 树）：
  • 时间：O(n log m)，其中 m 是去重后的值个数（需要离散化）。
  • 空间：O(n + m) 用于存储离散化映射和树状数组。
• 整数计数排序优化：
  • 时间：O(n + k)，k 是值域范围。
  • 空间：O(n + k)。

第五步：实现示例（基本稳定版本）
下面是基本稳定比较计数排序的 Python 实现，包含稳定性保证：

def comparison_counting_sort_stable(arr):
    n = len(arr)
    if n == 0:
        return arr
    count = [0] * n
    # 统计小于每个元素的个数
    for i in range(n):
        for j in range(n):
            if i != j and arr[j] < arr[i]:
                count[i] += 1
    # 从后向前放置元素以保持稳定
    output = [None] * n
    for i in range(n-1, -1, -1):
        pos = count[i]
        while output[pos] is not None:  # 处理冲突（实际上不会发生，因为count计算正确）
            pos += 1
        output[pos] = arr[i]
    return output

# 测试
arr = [4, 2, 2, 8]
sorted_arr = comparison_counting_sort_stable(arr)
print(sorted_arr)  # 输出: [2, 2, 4, 8]，稳定

注意：上述代码中的 while 循环在实际中不会执行，因为 count 计算准确，但保留以处理边界情况。更高效的实现可以直接用 output[count[i]] = arr[i] 然后调整 count，如前所述。

总结
比较计数排序的稳定版本通过统计“小于”个数和从后向前放置来实现稳定性。基本版本时间复杂度为 O(n²)，适合教学理解稳定性处理。通过引入树状数组等数据结构，可优化至 O(n log n) 级别，但在实际中，对可比较数据通常使用标准 O(n log n) 排序算法（如归并、快速）。此算法的核心价值在于展示计数定位与稳定性保证的结合。