问答题
在已排好序的序列中，一个元素所处的位置取决于具有更小排序码的元素的个数。基于这个思想，可得计数排序方法。假设待排序元素放在数组a[n]中，n是待排序元素个数。该方法建立一个计数数组count[n]，用count[i]记下在已排好序的序列中a[i]前面的元素个数，最后依count[]的值，将序列在a[n]中重新排列，就可完成排序。编写一个算法，实现计数排序，并说明对于一个有a个元素的序列，为确定所有元素的count值，最多需要做n(n-1)/2次排序码比较。
【正确答案】
【答案解析】这是一个典型的以空间换时间的例子。为了加速计数排序的排序速度，增设一个整数计数数组，存放待排序数据的各自存放位置，然后对号入座。如下图所示为一个计数排序的例子。
Typedef int DataType;
void count_sort(DataType a[],DataType R[],intn){
int i,j;int count[n]; //count[n]存放各元素地址计数
for(i=0;i＜n;i++) //count[n]初始化,计数值都为0
for(i=0;i＜n-1;i++)
for(j=i+1;j＜n;j++) //统计
if(a[j]＜a[i])count[i]++;
else count[j]++;
for(i=0;i＜n;i++)R[count[i]]=a[i]; //在R[]中各就各位
}
算法的排序码比较次数取决于代码中的二重循环，内层循环次数又取决于外层，有排序码比较次数=
Typedef int DataType;
void count_sort(DataType a[],DataType R[],intn){
int i,j;int count[n]; //count[n]存放各元素地址计数
for(i=0;i＜n;i++) //count[n]初始化,计数值都为0
for(i=0;i＜n-1;i++)
for(j=i+1;j＜n;j++) //统计
if(a[j]＜a[i])count[i]++;
else count[j]++;
for(i=0;i＜n;i++)R[count[i]]=a[i]; //在R[]中各就各位
}
算法的排序码比较次数取决于代码中的二重循环，内层循环次数又取决于外层，有排序码比较次数=