排序算法之：比较计数排序（Comparison Counting Sort）的进阶应用：稳定排序与空间优化 题目描述：给定一个包含n个元素的数组，每个元素可能包含多个属性（如值和索引），使用比较计数排序（Comparison Counting Sort）算法对数组进行稳定排序，并优化其空间复杂度。 解题过程： 基本比较计数排序原理 比较计数排序的核心思想是：对每个元素，统计数组中比它小的元素个数，这个计数结果就是该元素在排序后数组中的位置 基本步骤： a) 初始化计数数组count，长度与输入数组相同，全部设为0 b) 对于每个元素arr[ i]，遍历所有其他元素arr[ j ] c) 如果arr[ j] < arr[ i]，则count[ i ]增加1 d) 如果arr[ j] == arr[ i]且j < i（保持稳定性），count[ i ]增加1 e) 根据count数组将元素放到输出数组的对应位置 稳定性问题的解决 在存在相等元素时，需要保持原始相对顺序 修改比较条件：当arr[ j] == arr[ i]时，如果j < i，也要增加count[ i ] 这样确保相等元素中，原始位置靠前的元素在排序后仍然靠前 空间复杂度优化 原始算法需要O(n)的额外空间存储计数数组和输出数组 优化方案：使用原地重排技术 a) 先计算每个元素的目标位置 b) 通过循环交换将元素放到正确位置 c) 每次交换后，更新相关元素的计数信息 具体实现步骤 步骤1：初始化计数数组 创建数组count，长度n，初始化为0 步骤2：统计比较结果 使用双重循环： for i from 0 to n-1: for j from 0 to n-1: if i == j: continue if arr[ j] < arr[ i] or (arr[ j] == arr[ i] and j < i): count[ i ] += 1 步骤3：构建输出数组（稳定版本） 创建输出数组output，长度n for i from 0 to n-1: output[ count[ i]] = arr[ i ] 步骤4：空间优化版本 不创建输出数组，而是原地重排： i = 0 while i < n: pos = count[ i ] if pos == i: # 元素已在正确位置 i += 1 else: # 交换arr[ i]和arr[ pos]，同时交换count[ i]和count[ pos ] swap(arr[ i], arr[ pos ]) swap(count[ i], count[ pos ]) 时间复杂度分析 比较阶段：O(n²) - 每个元素与其他所有元素比较 重排阶段：O(n) - 每个元素最多交换一次 总体时间复杂度：O(n²) 适用场景与限制 适用于小规模数据排序 当比较操作代价较高时可能不适用 稳定排序版本保持原始相对顺序 空间优化版本将空间复杂度从O(n)降到O(1)（不计输入输出空间） 与其他排序算法比较 比冒泡排序、选择排序更直观易懂 在特定场景下（如需要稳定排序且数据量小）有优势 不适合大规模数据排序