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

题目描述
比较计数排序是一种非基于比较的排序算法，它通过统计每个元素在数组中应该出现的位置来实现排序。给定一个包含n个元素的数组，其中元素可能重复，请实现一个稳定版本的比较计数排序算法，确保相同元素的相对顺序在排序后保持不变，并分析其时间复杂度和空间复杂度。

解题过程

1. 基本思想理解
比较计数排序的核心思想是：对于数组中的每个元素，统计比它小的元素个数，这个数量就直接决定了该元素在排序后数组中的位置。比如有3个元素比某个元素小，那么这个元素就应该放在第4个位置（索引为3）。

2. 基本算法步骤

• 步骤1：创建一个计数数组count，长度与原始数组相同，初始化为0
• 步骤2：对于每个元素arr[i]，统计比它小的元素个数，存入count[i]
• 步骤3：根据count数组中的位置信息，将元素放到结果数组的相应位置

3. 稳定性问题分析
基本版本的比较计数排序是不稳定的，因为当遇到相同元素时，它们会被按照原始顺序的逆序放置。为了保持稳定性，我们需要调整统计方式。

4. 稳定版本的实现

步骤1：统计"小于等于"的数量

def comparison_counting_sort_stable(arr):
    n = len(arr)
    if n <= 1:
        return arr
    
    # 步骤1：初始化计数数组
    count = [0] * n
    
    # 步骤2：统计每个元素前面有多少个元素小于等于它
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                count[j] += 1
            else:
                count[i] += 1
    
    # 步骤3：创建结果数组并按正确位置放置元素
    result = [0] * n
    for i in range(n):
        result[count[i]] = arr[i]
    
    return result

5. 优化版本（处理重复元素）
上面的版本可以保证稳定性，但我们可以进一步优化，使其更清晰易懂：

def comparison_counting_sort_optimized(arr):
    n = len(arr)
    if n <= 1:
        return arr
    
    # 优化方法：先统计小于每个元素的个数，再处理相等情况
    count = [0] * n
    
    # 第一遍：统计严格小于的元素个数
    for i in range(n):
        for j in range(n):
            if arr[j] < arr[i]:
                count[i] += 1
    
    # 第二遍：处理相等元素，确保稳定性
    # 对于相等的元素，保持它们原来的相对顺序
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                count[j] = count[i] + 1
    
    # 放置元素到正确位置
    result = [0] * n
    for i in range(n):
        result[count[i]] = arr[i]
    
    return result

6. 逐步示例演示

以数组 [4, 2, 4, 1, 3] 为例：

步骤1：统计严格小于的元素个数

• 元素4：比它小的有2,1,3 → count[0] = 3
• 元素2：比它小的有1 → count[1] = 1
• 元素4：比它小的有2,1,3 → count[2] = 3
• 元素1：没有比它小的 → count[3] = 0
• 元素3：比它小的有2,1 → count[4] = 2

步骤2：处理相等元素

• 发现arr[0]和arr[2]都是4，且相等
• 保持相对顺序：count[2] = count[0] + 1 = 4

步骤3：最终位置分配

• result[3] = 4 (第一个4)
• result[1] = 2
• result[4] = 4 (第二个4)
• result[0] = 1
• result[2] = 3

排序结果：[1, 2, 3, 4, 4]（保持稳定性）

7. 复杂度分析

• 时间复杂度：O(n²) - 需要两层循环比较所有元素对
• 空间复杂度：O(n) - 需要额外的count数组和结果数组
• 稳定性：✓ 保证（通过处理相等元素的顺序）

8. 适用场景
比较计数排序适用于：

• 小规模数据排序
• 需要保证稳定性的场景
• 元素取值范围不大的情况

虽然时间复杂度较高，但该算法的思想是理解更复杂排序算法（如基数排序）的重要基础。