（6 分）已知某排序算法：void cmpCountS

（6 分）已知某排序算法：

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）该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。

【答案解析】

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

（3）不是稳定的，需要将程序中的 if 语句修改如下：

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

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