【说明】 冒泡排序算法,作为Orderedlist<T,size>类的成员函数,last是有序表的元素个数。 template<typename T,int size>void Orderedlist<T,size>∷BubbleSort(){ bool noswap; //交换标志 int i,j; T temp; for(i=0;i<last;i++) { noswap= (1) ; for(j= (2) ; (3) ; (4) ) {//从下往上冒泡 if(slist[j]<slist[j-1]) { temp=slist[j]; slist[j]=slist[j-1]; slist[j-1]=temp; noswap= (5) ; } } if(noswap)break; } }
参考答案:
解析:true (2)last (3)j>i
(4)j-- (5)false
[分析]:
本题考查用C++实现冒泡排序。
题目要求用程序实现冒泡排序,其中last是有序表的元素个数,即需排序元素的个数。首先我们需要了解一下冒泡排序的方法。冒泡排序将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看做是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上“飘浮”。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
冒泡排序的具体过程为:
第一步,先比较k1和k2,若k1>k2,则交换k1和k2所在的记录,否则不交换。继续对k2和k3重复上述过程,直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置,称第1次起泡,共执行n-1次比较。
第二步,与第一步类似,从k1和k2开始比较,到kn-2和kn-1为止,共执行n-2次比较,称第2次起泡。
依此类推,共做n-1次起泡,完成整个排序过程。下面我们来具体分析程序。
第(1)空很明显是给布尔型交换标志变量noswap赋一个初值,从程序中不难发现,这个变量为真时,当前元素才可以进行交换操作,那么其初值应该是一个为真的值,因此此空答案为true。
第(2)空是给循环变量赋一个初值,这个循环的作用注释已经给出,是从下往上冒泡。题目中告诉我们序列中有last个元素,那么最下面的元素应该是第last个,因此此空答案为last。
第(3)空是循环的判断条件,根据我们上面的分析,每次起泡需要比较的次数为:总元素个数-已经起泡的次数,起泡的过程只需要执行到当前已经排好序的最后一个元素即可,因此此空答案为j>i。
第(4)空也在循环中,很明显是用来改变循环变量j的值,而这个循环变量是从last开始依次往上的过程,因此循环变量j的值应该是每次减少1,所以此空答案为j--。
第(5)空是给布尔型交换标志变量noswap赋一个值,它在循环的最后面,也就是说,在一次冒泡排序结束时的操作,根据题目的分析我们可以知道,每次冒泡排序都能排好一个元素在序列中的位置,而这个已经排好序的元素以后就不需要再参加排序过程了,因此应该将其标志变量noswap赋一个假值,因此此空答案为false。