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

字数 3138 2025-12-16 22:25:37

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

题目描述：
给定一个包含 n 个元素的数组 arr，每个元素都是整数（可包含负数、重复值，且范围可能较大）。我们需要实现一个稳定的比较计数排序（Comparison Counting Sort）算法，使其时间复杂度为 O(n²) 的比较计数版本优化为 O(n + k) 的稳定版本，其中 k 是数组中不同值的范围大小。该算法应能正确处理负数，并保证排序的稳定性（即相等元素的相对顺序保持不变）。你需要详细讲解其优化思路、实现步骤，并分析时间与空间复杂度。

解题过程循序渐进讲解：

步骤1：理解基础比较计数排序的原理
基础比较计数排序的核心思想是：对每个元素，统计数组中比它小的元素个数，这个计数就直接决定了该元素在输出数组中的位置。

具体做法：使用一个计数数组 count，对于每个索引 i，遍历整个数组统计有多少元素小于 arr[i]，将统计结果存入 count[i]。然后根据 count[i] 将 arr[i] 放到输出数组的对应位置。
缺点：
- 时间复杂度为 O(n²)，因为有两层嵌套循环（每个元素都要和所有其他元素比较）。
- 不稳定：当有重复元素时，先被遍历的重复元素可能被后放置，破坏稳定性。
- 无法直接处理负数（因为计数数组的索引通常从0开始）。

步骤2：优化思路——利用前缀和实现稳定排序
我们可以将算法优化为稳定排序，并同时支持负数，步骤如下：

确定值范围：
找出数组中的最小值 minVal 和最大值 maxVal，计算值范围 size = maxVal - minVal + 1。
这将允许我们把负数偏移到非负索引（例如，值 x 映射到索引 x - minVal）。
第一次遍历：频率统计
创建一个长度为 size 的数组 freq，初始化为0。
遍历原数组 arr，对于每个元素 arr[i]，计算其映射索引 idx = arr[i] - minVal，然后 freq[idx]++。
这一步统计每个值出现的次数，时间复杂度 O(n)。
第二次遍历：计算前缀和
对 freq 数组计算前缀和，使得 prefix[i] 表示原数组中小于等于值 i + minVal 的元素个数。
具体计算：
- 第一种方法：直接累加，prefix[0] = freq[0]，对于 i > 0，prefix[i] = prefix[i-1] + freq[i]。
- 第二种方法（更常见于稳定排序）：让 prefix[i] 表示“严格小于值 i + minVal 的元素个数”，即从0开始累加，但先不包含当前值。这里我们采用第二种，因为它能更方便地实现稳定排序（稍后解释）。
第三种前缀和计算（稳定排序关键）：
我们实际需要的是“每个值在输出数组中的起始位置”。
定义 pos 数组，长度 size，初始化 pos[0] = 0，然后对于 i = 1 to size-1，pos[i] = pos[i-1] + freq[i-1]。
这样，pos[idx] 就表示值 arr[i] 在输出数组中第一个出现的位置索引。
例如，如果值为 v 的元素有3个，那么它们会占据输出数组的 pos[idx]、pos[idx]+1、pos[idx]+2 这三个位置。
第三次遍历：放置元素到输出数组
创建一个输出数组 output，长度 n。
遍历原数组 arr（从前往后遍历以保证稳定性），对每个 arr[i]：
- 计算映射索引 idx = arr[i] - minVal。
- 将 arr[i] 放到 output[pos[idx]]。
- 然后 pos[idx]++（为下一个相同值的元素腾出位置）。
  这样，相同值的元素会按照在原数组中的顺序依次放置，从而保证稳定性。
第四次遍历：回写原数组（如果需要原地排序）
将 output 数组拷贝回原数组 arr。

步骤3：实例演示
假设 arr = [4, -1, 4, 2]：

minVal = -1，maxVal = 4，size = 4 - (-1) + 1 = 6。
频率统计 freq：值映射：-1→0, 0→1, 1→2, 2→3, 3→4, 4→5。
得到 freq = [1, 0, 0, 1, 0, 2]（对应值 -1,0,1,2,3,4 的频率）。
计算 pos 数组（起始位置）：
pos[0] = 0（值 -1 起始位置0）
pos[1] = pos[0] + freq[0] = 0 + 1 = 1（值0起始位置1）
pos[2] = pos[1] + freq[1] = 1 + 0 = 1（值1起始位置1）
pos[3] = pos[2] + freq[2] = 1 + 0 = 1（值2起始位置1）
pos[4] = pos[3] + freq[3] = 1 + 1 = 2（值3起始位置2）
pos[5] = pos[4] + freq[4] = 2 + 0 = 2（值4起始位置2）
实际上，我们只需要计算到有值的索引，但这里为清晰展示全部计算。
放置元素（按原数组顺序）：
- arr[0]=4 → idx=5 → 放到 output[pos[5]=2] → output[2]=4，pos[5]++变为3。
- arr[1]=-1 → idx=0 → 放到 output[0]=-1，pos[0]++变为1。
- arr[2]=4 → idx=5 → 放到 output[pos[5]=3] → output[3]=4，pos[5]++变为4。
- arr[3]=2 → idx=3 → 放到 output[pos[3]=1] → output[1]=2，pos[3]++变为2。
  最终 output = [-1, 2, 4, 4]，是稳定排序。

步骤4：算法复杂度分析

时间复杂度：
统计频率 O(n)，计算前缀和 O(k)（k 是值范围大小），放置元素 O(n)，回写 O(n)。
总计 O(n + k)，当 k = O(n) 时，为线性时间。
空间复杂度：
需要额外数组：freq 和 pos 长度 k，输出数组长度 n。
总计 O(n + k)。可以优化为只用一个 prefix 数组（长度 k+1）结合频率数组，但通常保留输出数组以保证稳定性。

步骤5：边界条件与注意事项

当 k 很大（例如值范围远超 n）时，此算法可能不如基于比较的排序高效，此时应考虑其他非比较排序（如基数排序）。
如果数组元素是浮点数，可以先乘以一个倍数转为整数（但需注意精度）。
稳定性由遍历原数组的顺序和 pos 数组的更新方式保证，务必从前往后遍历原数组，并且 pos 初始化为起始位置而非前缀和。

总结：
比较计数排序的优化版本通过频率统计和前缀和计算，将原始的 O(n²) 稳定排序优化为 O(n + k) 的稳定排序。它适用于值范围 k 不大的整数排序场景，且能天然支持负数。此算法本质上是计数排序的一种实现，但重点在于前缀和计算与稳定放置的细节，这是理解线性时间稳定排序的关键步骤。

排序算法之：比较计数排序（Comparison Counting Sort）的进阶优化：前缀和计算与稳定排序的实现优化题目描述：给定一个包含 n 个元素的数组 arr ，每个元素都是整数（可包含负数、重复值，且范围可能较大）。我们需要实现一个稳定的比较计数排序（Comparison Counting Sort）算法，使其时间复杂度为 O(n²) 的比较计数版本优化为 O(n + k) 的稳定版本，其中 k 是数组中不同值的范围大小。该算法应能正确处理负数，并保证排序的稳定性（即相等元素的相对顺序保持不变）。你需要详细讲解其优化思路、实现步骤，并分析时间与空间复杂度。解题过程循序渐进讲解：步骤1：理解基础比较计数排序的原理基础比较计数排序的核心思想是：对每个元素，统计数组中比它小的元素个数，这个计数就直接决定了该元素在输出数组中的位置。具体做法：使用一个计数数组 count ，对于每个索引 i ，遍历整个数组统计有多少元素小于 arr[i] ，将统计结果存入 count[i] 。然后根据 count[i] 将 arr[i] 放到输出数组的对应位置。缺点：时间复杂度为 O(n²) ，因为有两层嵌套循环（每个元素都要和所有其他元素比较）。不稳定：当有重复元素时，先被遍历的重复元素可能被后放置，破坏稳定性。无法直接处理负数（因为计数数组的索引通常从0开始）。步骤2：优化思路——利用前缀和实现稳定排序我们可以将算法优化为稳定排序，并同时支持负数，步骤如下：确定值范围：找出数组中的最小值 minVal 和最大值 maxVal ，计算值范围 size = maxVal - minVal + 1 。这将允许我们把负数偏移到非负索引（例如，值 x 映射到索引 x - minVal ）。第一次遍历：频率统计创建一个长度为 size 的数组 freq ，初始化为0。遍历原数组 arr ，对于每个元素 arr[i] ，计算其映射索引 idx = arr[i] - minVal ，然后 freq[idx]++ 。这一步统计每个值出现的次数，时间复杂度 O(n) 。第二次遍历：计算前缀和对 freq 数组计算前缀和，使得 prefix[i] 表示原数组中小于等于值 i + minVal 的元素个数。具体计算：第一种方法：直接累加， prefix[0] = freq[0] ，对于 i > 0 ， prefix[i] = prefix[i-1] + freq[i] 。第二种方法（更常见于稳定排序）：让 prefix[i] 表示“严格小于值 i + minVal 的元素个数”，即从0开始累加，但先不包含当前值。这里我们采用第二种，因为它能更方便地实现稳定排序（稍后解释）。第三种前缀和计算（稳定排序关键）：我们实际需要的是“每个值在输出数组中的起始位置”。定义 pos 数组，长度 size ，初始化 pos[0] = 0 ，然后对于 i = 1 to size-1 ， pos[i] = pos[i-1] + freq[i-1] 。这样， pos[idx] 就表示值 arr[i] 在输出数组中第一个出现的位置索引。例如，如果值为 v 的元素有3个，那么它们会占据输出数组的 pos[idx] 、 pos[idx]+1 、 pos[idx]+2 这三个位置。第三次遍历：放置元素到输出数组创建一个输出数组 output ，长度 n 。遍历原数组 arr （从前往后遍历以保证稳定性），对每个 arr[i] ：计算映射索引 idx = arr[i] - minVal 。将 arr[i] 放到 output[pos[idx]] 。然后 pos[idx]++ （为下一个相同值的元素腾出位置）。这样，相同值的元素会按照在原数组中的顺序依次放置，从而保证稳定性。第四次遍历：回写原数组（如果需要原地排序）将 output 数组拷贝回原数组 arr 。步骤3：实例演示假设 arr = [4, -1, 4, 2] ： minVal = -1 ， maxVal = 4 ， size = 4 - (-1) + 1 = 6 。频率统计 freq ：值映射：-1→0, 0→1, 1→2, 2→3, 3→4, 4→5。得到 freq = [1, 0, 0, 1, 0, 2] （对应值 -1,0,1,2,3,4 的频率）。计算 pos 数组（起始位置）： pos[0] = 0 （值 -1 起始位置0） pos[1] = pos[0] + freq[0] = 0 + 1 = 1 （值0起始位置1） pos[2] = pos[1] + freq[1] = 1 + 0 = 1 （值1起始位置1） pos[3] = pos[2] + freq[2] = 1 + 0 = 1 （值2起始位置1） pos[4] = pos[3] + freq[3] = 1 + 1 = 2 （值3起始位置2） pos[5] = pos[4] + freq[4] = 2 + 0 = 2 （值4起始位置2）实际上，我们只需要计算到有值的索引，但这里为清晰展示全部计算。放置元素（按原数组顺序）： arr[0]=4 → idx=5 → 放到 output[pos[5]=2] → output[ 2]=4，pos[ 5 ]++变为3。 arr[1]=-1 → idx=0 → 放到 output[ 0]=-1，pos[ 0 ]++变为1。 arr[2]=4 → idx=5 → 放到 output[ pos[ 5]=3] → output[ 3]=4，pos[ 5 ]++变为4。 arr[3]=2 → idx=3 → 放到 output[ pos[ 3]=1] → output[ 1]=2，pos[ 3 ]++变为2。最终 output = [ -1, 2, 4, 4 ]，是稳定排序。步骤4：算法复杂度分析时间复杂度：统计频率 O(n) ，计算前缀和 O(k) （k 是值范围大小），放置元素 O(n) ，回写 O(n) 。总计 O(n + k) ，当 k = O(n) 时，为线性时间。空间复杂度：需要额外数组： freq 和 pos 长度 k ，输出数组长度 n 。总计 O(n + k) 。可以优化为只用一个 prefix 数组（长度 k+1 ）结合频率数组，但通常保留输出数组以保证稳定性。步骤5：边界条件与注意事项当 k 很大（例如值范围远超 n ）时，此算法可能不如基于比较的排序高效，此时应考虑其他非比较排序（如基数排序）。如果数组元素是浮点数，可以先乘以一个倍数转为整数（但需注意精度）。稳定性由遍历原数组的顺序和 pos 数组的更新方式保证，务必从前往后遍历原数组，并且 pos 初始化为起始位置而非前缀和。总结：比较计数排序的优化版本通过频率统计和前缀和计算，将原始的 O(n²) 稳定排序优化为 O(n + k) 的稳定排序。它适用于值范围 k 不大的整数排序场景，且能天然支持负数。此算法本质上是计数排序的一种实现，但重点在于前缀和计算与稳定放置的细节，这是理解线性时间稳定排序的关键步骤。