第42题
（6 分）已知某排序算法：
1 2 3 4 5 6 7 8 9 10 11 12 | 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）该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。
【答案解析】
cmpCountSort 算法基于计数排序的思想，对序列进行排序。cmpCountSort 算法遍历数组中的元素，count 数组记录比对应待排序数组元素下标大的元素个数，例如，count[1]=3 的意思是数组 a 中有 3 个元素比 a[1]大，即 a[1]是第 4 大元素，a[1]的正确位置应是 b[3]。
（1）数组 b[ ]={-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 语句修改如下：
1 2 | if(a[i]<=a[j]) count[j]++;
else count[i]++;
|
如果不加等号，两个相等的元素比较时，前面元素的 count 值会加 1，导致原序列中靠前的元素在排序后的序列中处于靠后的位置。