已知某排序算法如下： void cmpCountSort(int a[],int b[],int_

[数据结构 P2017] 已知某排序算法如下： void cmpCountSort(int a[],int b[],int

学习人数: 653

正确率: ??%

题目描述

未通过

已知某排序算法如下：

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; 
}

请回答下列问题。

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

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

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

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

1 个回答 (点击展开回答)

TWua

2024年11月18日 10:30

（1）-10，10，11，19，20，25

（2）n(n-1)/2

（3）不稳定
稳定排序算法：

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;

}

参考答案

解答：

⑴ 为了区分两个25...

用户登录可进行刷题及查看答案

解答：

⑴ 为了区分两个25不同，将后一个25标粗，int a[] = {25, -10, 25, 10, 11, 19}。这道题的思想不复杂，采用了计数排序思想，简单描述就是要count数组用于计算数组中有几个元素小于当前元素，比这个元素小的元素越多，这个元素权重越大，这个元素最终也越靠后，然后就能以此为依据进行排序。我们很容易计算出count[] = {5, 0, 4, 1, 2, 3}，可得：

b = {-10, 10, 11, 19, 25, 25}。

⑵ 由for循环代码可知，每个元素需要和它后面的元素都比较一次，得到 (n−1)+(n−2)+⋯+1=n(n−1)/2 。

⑶ 很显然，这个算法不稳定，观察代码：

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

本质就是：

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

调整前后相同元素的权重，给后面的元素权重大一点，移动下等于情况就行，即：

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

简化为：

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

所以只需要修改第6行代码为：

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

这样就能解决问题。

tips：这种题如果上来没看出门道，按照代码执行顺序模拟一遍就能看出题目想表达的意思了，考场上要做到沉着冷静。