题目

已知某排序算法如下：

void cmpCountSort(int a[], int b[], int n) {
    int i, j, *count;
    count = (int *)malloc(sizeof(int) * n);   // C++ 语言：count = new int[n];
    for (i = 0; i < n; i++) count[i] = 0;
    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (a[i] < a[j]) count[j]++;
            else            count[i]++;
    for (i = 0; i < n; i++) b[count[i]] = a[i];
    free(count);   // C++ 语言：delete count;
}

请回答下列问题：

(1) 若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6];，则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么？

(2) 若 a 中含有 n 个元素，则算法执行过程中，元素之间的比较次数是多少？

(3) 该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。

解析

算法本质：count[k] 是 a[k] 在数组中的最终排名（从 0 起）

编者注（生僻术语）：这就是经典的「比较计数排序 / Comparison Counting Sort」。它跟桶式的 Counting Sort（值域计数）完全是两个东西，别混。本题的 count[] 数组不是值域桶，而是"每个原位置元素的最终排名"。

外层 i + 内层 j（i < j）枚举所有"位置对"：

• a[i] < a[j] → count[j]++（j 处的元素被发现"大于"了一个，排名 +1）；
• 否则（包括相等）→ count[i]++（i 处的元素排名 +1）。

每对位置贡献恰好 1 次累加，n 个元素共 对。最后 count[i] = a[i] 的最终下标，所以 b[count[i]] = a[i] 一遍写就排好了。

(1) 给定数组的 b 内容

答案：b = [-10, 10, 11, 19, 25, 25]。

逐对模拟（n = 6）。下表记录每一轮内层循环结束后 count[] 的累加：

i	内层循环 (j 与判断)	对 count 的累加	累计 count
0 (a=25)	j=1..5 共 5 对，全是 25 ≥ a[j]，均 count[0]++	count[0]+=5	[5,0,0,0,0,0]
1 (a=−10)	j=2..5，−10 < a[j] 全成立，分别 count[j]++	count[2,3,4,5] 各+1	[5,0,1,1,1,1]
2 (a=25)	j=3..5，25 ≥ a[j] 全成立，均 count[2]++	count[2]+=3	[5,0,4,1,1,1]
3 (a=10)	j=4 (10<11) → count[4]++；j=5 (10<19) → count[5]++	count[4,5] 各+1	[5,0,4,1,2,2]
4 (a=11)	j=5 (11<19) → count[5]++	count[5]+=1	[5,0,4,1,2,3]
5	(内层 0 对)	—	[5,0,4,1,2,3]

最终 count = [5, 0, 4, 1, 2, 3]。按 b[count[i]] = a[i] 散列回去：

i	a[i]	count[i]	写入
0	25	5	b[5] = 25
1	−10	0	b[0] = −10
2	25	4	b[4] = 25
3	10	1	b[1] = 10
4	11	2	b[2] = 11
5	19	3	b[3] = 19

得 b = [−10, 10, 11, 19, 25, 25]。

(2) 元素之间的比较次数

答案： 次（n = 6 时为 15 次）。

外层 i 取 0..n−2，内层 j 取 i+1..n−1：

每对 (i, j) 恰好比较 1 次（if (a[i] < a[j]) 这一行）。比较次数与输入数据无关，永远是 。

(3) 稳定性 + 改造为稳定

答案：原算法不稳定。修改：把 if (a[i] < a[j]) 改为 if (a[i] <= a[j])。

为什么原算法不稳定：本例中两个 25（原位置 0 与 2）排序后落到位置 5 和 4——原本靠前的 25 跑到了靠后，相对顺序颠倒。

根因在于代码遇到相等时走 else 分支：当 i < j 且 a[i] == a[j] 时，count[i]++，靠前的位置反而排名更大，结果靠前的元素被推到后面。

修改方法：让"相等"也走 count[j]++——即靠后的位置排名 +1，靠前的保留小排名：

for (i = 0; i < n - 1; i++)
    for (j = i + 1; j < n; j++)
        if (a[i] <= a[j]) count[j]++;     // 改 < 为 <=
        else              count[i]++;

验证修改后稳定：再跑一次本例，i=0、j=2 时 a[0]=25, a[2]=25，25 ≤ 25 成立 → count[2]++，count[0] 不变。最终位置 0 的 25 排名仍为 4（少 1），位置 2 的 25 排名为 5——原顺序保持，稳定。

编者注（生僻术语）：「稳定排序」指对所有相等关键字，排序后的相对顺序与排序前一致。判断方法是构造一个有重复关键字的输入，看输出里相等元素的相对位置是否颠倒——本题第 (1) 问的 a 中两个 25 就是天然的稳定性测试用例，可见命题人本意就是引出 (3)。