C++计数排序详解：原理、代码与稳定性分析

结果与目标

计数排序的目标是将输入数组 A 中的整数有序地排列到输出数组 B 中。其核心假设是输入数据均为介于 0 到 k 之间的整数。算法的时间复杂度为 O(n+k)，在 k 不大于 n 时具有线性时间优势。

准备条件

为了实现计数排序，需要准备三个关键数据结构：

1. 输入数组 A：长度为 n，包含待排序的整数。
2. 输出数组 B：长度同样为 n，用于存放最终排序结果。
3. 计数数组 C：长度为 k+1（k 为数组 A 中的最大值），用于统计每个元素出现的频次及累积位置。

真实操作顺序

第1步：确定最大元素值 k

首先需要遍历输入数组，找到其中的最大值，以确定计数数组 C 的大小。这一步确保了后续内存分配的正确性。

int count_k(int A[], int length)
{
  int j, max;
  max = A[0];
  for(j=1; j<=length-1; j++)
  {
    if(A[j] >= max)
      max = A[j];
  }
  return max;
}

第2步：初始化计数数组 C

根据上一步得到的最大值 k，动态分配并初始化计数数组 C，将所有元素设为 0。

第3步：统计元素频次

遍历输入数组 A，将每个元素作为索引在 C 中进行累加。例如，若数组 A 中有 2 个 0、2 个 2、3 个 3 等，则 C[A[j]] 记录了原始值的出现次数。

// 计算A中各元素的个数
for(j=0; j<=length-1; j++)
  C[A[j]] = C[A[j]] + 1;

第4步：计算累积位置

这是计数排序的关键步骤。将 C[i] 修改为“小于等于 i 的元素个数”。这使得 C[x] 的值直接对应于元素 x 在输出数组 B 中的最终位置索引（需减1）。

// 计算小于等于C[i]的元素的个数
for(i=1; i<=k; i++)
  C[i] = C[i] + C[i-1];

第5步：倒序填充输出数组 B

最后，再次遍历输入数组 A，但此次必须从后往前进行。对于每个元素 A[j]：

1. 利用当前 C[A[j]] 的值确定其在 B 中的位置索引 k = C[A[j]] - 1。
2. 将 A[j] 放入 B[k]。
3. 将 C[A[j]] 减 1，以便处理下一个相同的元素。

// 倒序放置元素以保证稳定性
for(j=length-1; j>=0; j--)
{
  int k = C[A[j]] - 1;
  B[k] = A[j];
  C[A[j]] = C[A[j]] - 1;
}

此过程通过多次迭代将分散的元素填入正确位置，具体每一步的位置映射变化如下所示：

完成所有元素放置后的最终排序结果如图：

第6步：释放内存

由于计数数组 C 是使用 malloc 动态分配的，使用后必须调用 free(C) 防止内存泄漏。

完成判断与排错

排序稳定性的保证：
在第五步中，遍历输入数组 A 的顺序至关重要。必须从右向左（倒序）遍历。当遇到相同值的元素时，后出现的元素会被先放入较高的位置，先出现的元素被放入较低的位置。这种“后进先出”的逻辑确保了相等元素的相对顺序不变，从而实现了排序的稳定性。这一点在基数排序等多轮排序算法中具有决定性作用。

简要总结

以上就是C++实现计数排序的详细解析，涵盖了从原理分析、代码实现到稳定性证明的完整流程。更多关于算法基础与优化技巧的资料，请关注本站其它相关文章！