数据结构
2021-42
已知某排序算法如下：
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）该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。
答案
1） 调用 cmpCountSort(a, b, 6) 后，数组 b 的内容为 {-10, 10, 11, 19, 25, 25}。
2） 算法执行过程中，元素之间的比较次数为 n(n-1)/2。
3） 该算法不是稳定的。
理由：原数组中相同的元素（如两个 25）在排序后相对顺序发生了改变（第一个 25 出现在第二个 25 之后）。
修改为稳定排序算法的方法：在比较 a[i] 和 a[j] 时，当两者相等时，应根据下标 i 和 j 的大小来决定增加 count[i] 还是 count[j]。例如，可修改比较逻辑为：
if (a[i] < a[j] || (a[i] == a[j] && i < j))
count[j]++;
else
count[i]++;