第 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) 该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。
[tag_link]
cmpCountSort 算法基于计数排序的思想，对序列进行排序。cmpCountSort 算法遍历数组中的元素，count 数组记录比对应待排序数组元素下标大的元素个数，例如，count[1]=3的意思是数组 a 中有 3 个元素比 a[1]大，即 a[1]是第 4 大元素，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，导致原序列中靠前的元素在排序后的序列中处于靠后的位置。