题3

题3

题目

【2021 统考真题】已知某排序算法如下:

void cmpCountSort(int a[], int b[], int n) {
    int i, j, *count;
    count = (int * )malloc(sizeof(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);
}

请回答下列问题。

1. 若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6];,则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么?
2. 若 a 中含有 n 个元素,则算法执行过程中,元素之间的比较次数是多少?
3. 该算法是稳定的吗? 若是, 阐述理由; 否则, 修改为稳定排序算法。

分析

显然这是基于比较实现的一套算法，现在直接模拟一下
不稳定，因为算法结果是让序列从小到大排序，如果两个元素相同，判断条件a[i]<a[j]，两个相同相邻元素比较以后，前面的会多统计一个count，这将被视为是一个更大的数字，然后从小到大排序时，也就被放到了后面，然后交换了原始序列里的顺序。我们直接把这个判断条件调整为a[i]<=a[j]，让后一个元素+1，用这个加1，来维持它们的相对位置，表示自己是序列中靠后的
下面我这里做的时候，题目被错误ocr了，导致少了两个元素，但是大概的意思是不变的

解

cmpCountSort 算法基于计数排序的思想, 对序列进行排序。cmpCountSort 算法遍历数组中的元素, count 数组记录比对应待排序数组元素下标大的元素个数, 例如, count [1] =3 的意思是数组 a 中有三个元素比 a[1] 小,即 a[1] 是第四大元素, a[1] 的正确位置应是 b[3] 。

1. 排序结果为 b[6] = {-10, 10, 11, 19, 25, 25} 。
2. 由代码 for (i = 0; i < n - 1; i++) 和 for (j = i + 1; j < n; j++)
   可知,在循环过程中,每个元素都与它后面的所有元素比较一次 (即所有元素都两两比较一次), 比较次数之和为 (n - 1) + (n - 2) + ... + 1 ,所以总比较次数是 n * (n - 1) / 2 。
3. 不是。需要将程序中的 if 语句修改如下:

if (a[i] <= a[j]) count[j]++;
else count[i]++;

若不加等号, 两个相等的元素比较时, 前面元素的 count 值会加 1 , 则导致原序列中靠前的元素在排序后的序列中处于靠后的位置。