问答题 阅读下列说明和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语言实现。
(1)常量和变量说明
R:常量,定义元素取值范围中的取值个数,如上述应用中R值应取6
i:循环变量
n:待排序元素个数
a:输入数组,长度为n
b:输出数组,长度为n
c:辅助数组,长度为R,其中每个元素表示小于等于下标所对应的元素值的个数
(2)函数sort
void sort(intn, int a[], intb[]){
intc[R], i;
for (i=0; i<______; i++){
c[i]=0;
}
for(i=0; i<n; i++){
c[a[i]]=______;
}
for(i=1; 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] 本题考查排序的相关内容。
题目告诉我们排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m个位置。对于元素值重复的情况,依次放入第m-1、m-2……的位置。而且题目告诉我们算法的步骤。
下面我们来具体分析本试题。第1空所处的位置为函数sort()中第1个for循环中,从题目的描述和程序不难看出该循环的作用是给数组c赋初值,而根据题目描述可知数组c是一个辅助数组,长度为R,因此第1空应填R。
第2空在函数sort()中的第2个for循环中,很显然第2空是给数组c赋值,而且其下标为数组a的相应的元素值。再根据题目的描述“c数组中每个元素表示小于等于下标所对应的元素值的个数”,很显然,这个for循环的作用是统计每个元素值的个数,因此第2空的答案应该是c[a[i]]+1。
第3空在第3个for循环中,而且第3空是给出数组c赋值,根据题目提供的算法的步骤,我们可知,这个时候应该要统计小于等于每个元素值的个数,而等于的元素个数记录在c[i]中,小于的元素个数记录在c[i-1]中,因此第3空的答案是c[i]+c[i-1]。
第4空在最后一个for循环中,按题目要求,我们可以知道该for循环应该完成剩余的步骤3,即将输入元素序列中的每个元素放入有序的输出元素序列。而第4空是给数组b赋值,题目告诉我们b是输出数组,而a是输入数组,那么应该是将a中的值赋值给b中,因此第(4)空的答案应该为a[i]。
问答题 根据C代码,函数的时间复杂度和空间复杂度分别为______和______(用字母O符号表示)。
【正确答案】
【答案解析】O(n+R)或者O(n)或n或线性
O(n+R)或者O(n)或n或线性 本题主要考查时间复杂度与空间复杂度的分析。
首先我们来看空间复杂度,空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。在sort()函数中,声明了两个整型变量n和i(可忽略),两个整型数组b和c,而a不属于函数sort的临时空间,因此函数sort()的空间复杂度为O(n+R),这里由于在本题中R的值为6,因此也可以忽略,所以答案也可以是O(n)。
接着我们来分析时间复杂度,时间复杂度是度量算法执行的时间长短,函数sort()中有4个循环,其中有两个循环n次,而另外两个分别循环R-1和R次,因此时间复杂度应该为O(n+R),由于R的值为6,这里可以忽略,因此答案也可以是O(n)。
问答题 根据以上C代码,分析该排序算法是否稳定。若稳定,请简要说明(不超过100字);若不稳定,请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。
【正确答案】
【答案解析】不稳定。修改第12行的for循环为for(i=n-1; i>=0; i--)即可。所谓稳定性是指两个关键字相等的元素在排序前后的相对位置不发生变化,一般来讲,只要排序过程中比较和移动操作发生在相邻的元素间,排序方法是稳定的。本题中的排序是不稳定的,修改第12行的for循环为fOr(i=n=1; i>=0; i--),即可变得稳定。