问答题
阅读下列说明和C代码，回答下面问题。
[说明]
某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m个位置。对于元素值重复的情况，依次放入第m-1、m-2……个位置。例如，如果元素值小于等于4的元素个数有10个，其中元素值等于4的元素个数有3个，则4应该在数据元素序列的第10个位置、第9个位置和第8个位置上。
算法具体的步骤为：
步骤1：统计每个元素值的个数。
步骤2：统计小于等于每个元素值的个数。
步骤3：将输入元素序列中的每个元素放入有序的输出元素序列。
[C代码]
下面是该排序算法的C语言实现。
(1)常量和变量说明
●R：常量，定义元素取值范围中的取值个数，如上述应用中R值应取6。
●i：循环变量。
●n：待排序元素个数。
●a：输入数组，长度为n。
●b：输出数组，长度为n。
●c：辅助数组，长度为R，其中每个元素表示小于等于下标所对应的元素值的个数。
(2)函数sort
void sort(int n,int a[ ],int b[ ])
{
int c[R], i;
for(i=0;i＜______; i++)
{
c[i]=0;
}
for(i=0;i＜n;i++)
{
c[a[i]]=______;
}
for(i=0; i＜R; i++)
{
c[i]=______;
}
for(i=0;i＜n; i++)
{
b[c[a[i]]-1]=______;
c[a[i]]=c[a[i]]-1;
}
}
问答题
根据说明和C代码，填充C代码中的空缺。
【正确答案】
【答案解析】R； c[a[i]]+1； c[i]+c[i-1]； a[i]
[解析] 在函数sort中，首先对辅助数组C进行初始化，将R个元素全部初始化为0，代码为：
for({i=0;i＜R;i++)
{
c[i]=0;
}
然后，统计每个元素值的个数，元素的个数保存数组c中，c的下标表示对应的元素。通过循环读取元素a[i]，每读取到一个a[i]，c[a[i]]的值变加1，代码如下：
for(i=0; i＜n;i++)
{
c[a[i]]=c[a[i]]+1;
}
接下来统计小于等于每个元素值的个数，用c[i]保存。输入数组的每个元素的取值在0～5之间，即有6种取值，0、1、2、3、4、5，则c[0]保存的是值为0的元素个数，c[1]保存的是值为1的元素个数，以此类推，c[5]保存的是值为5的元素个数。则小于等于0的元素个数有c[0]个，小于等于1的元素有c[0]+c[1]个，小于等于2的元素有c[0]+c[1]+c[2]个，依次类推，小于等于5的元素个数为c[0]+c[1]+c[2]+c[3]+c[4]+c[5]。代码为：
for(i=0; i＜R; i++)
{
c[i]=c[i]+c[i-1];
}
最后，将输入元素序列中的每个元素放入有序的输出元素序列。小于等于a[i]的元素有c[a[i]]个，由于c语言中，数组的下标从0开始，每读取的一个值为a[j]的元素，应保存到b[c[a[i]]-1]，然后将c[a[i]]的值减1，c[a[i]]保存当前未保存到数组be的值为a[i]的元素个数。代码为：
for(i=0;i＜n; i++)
{
b[c[a[i]]-1]=a[i];
c[a[i]]=c[a[i]-1;
}
问答题
根据C代码，函数的时间复杂度和空间复杂度分别为______和______(用O符号表示)。
【正确答案】
【答案解析】O(n+R)，或者O(n)
O(R)，或者O(1)
[解析] 算法中只有单层循环，因此算法的时间复杂度为O(n+R)。
算法中需要用到一个长度为R的辅助数组c，因此算法的空间复杂度为O(R)。
问答题
根据以上C代码，分析该排序算法是否稳定。若稳定，请简要说明(不超过100字)；若不稳定，请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
【正确答案】
【答案解析】不稳定。修改第12行的for循环为：for(i=n-1;i＞=0;i--)即可，代码略。
[解析] 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。题目中，从下标0开始读取a[i]元素，第一个读取的值为a[i]的元素保存在b[c[a[i]]-1．，第二个读取的a[i]的元素保存在b[c[a[i]]-2]，也就是说读取的值为a[i]的元素保存在前面，因此该算法是不稳定的，只需将最后一个for循环改为如下代码即可变为稳定的。
for(i=n-1;i＞=0;i--)
{
b[c[a[i]]-1]=a[i];
c[a[i]]=c[a[i]]-1;
}