热心网友
9。2。1 冒泡排序 把记录序列图示成上下（或左右）次序，如右图，记录R1,R2,…,Rn序列为自下而上排列（即R1在最下面，Rn在最上面）。记录交换的方法是自下而上（或从左到右）比较相邻记录的关键词Kj和Kj+1 ．若Kj＞Kj+1，则互换Rj和Rj+1 ．这样，进行一趟比较，我们至少把具有最大关键词的记录送到最上边（或最右边，相应右图所示的“——”线），因此下一趟的比较次数将至少减少一次 。 算法BSort ( R，n ) // 冒泡排序算法，该算法对n个记录R1，R2，…，Rn进行排序 BS1 [冒泡过程]FOR i = n TO 2 STEP –1 DO FOR j = 1 TO i–1 DO IF Kj Kj+1 THEN ( RjRj+1 ) ?算法中关键词的比较次数为 可以减少算法中的关键词的比较次数吗？ 我们对如下9个元素执行冒泡排序： 07 09 02 16 08 05 12 13 14算法执行完第一次冒泡过程之后，记录序列变成如下：07 02 09 08 05 12 13 14 16按照算法BSort，下一次冒泡操作从第一个元素到第八个元素，记录序列变成如下：02 07 08 05 09 12 13 14 16最后一次记录交换发生在第四和第五个元素之间，事实上，下一次冒泡过程我们不必要从第一个元素检查到第七个元素，因为从第五个元素之后的所有元素已经排序完毕，因此下一次的冒泡循环到第四个元素就可以结束了，这样可以减少算法的关键词比较次数。 因此可以得出结论：在每一趟的比较中，当比较结束后，如果发现从某个位置t开始，不再进行记录交换，即说明从Rt+1～Rn已经排序（证明留作练习），从而下一趟的比较只要进行到位置t即可。据此我们可以给出一种改进的冒泡排序算法。 算法Bubble ( R，n )Bubble1 [终止位置初始化]BOUND n ． Bubble2 [冒泡过程]WHILE BOUND≠0 DO ( t 0 ． // t用来记录一趟冒泡最后记录交换的位置 FOR j＝1 TO BOUND-1 DOIFKjKj+1THEN(RjRj+ )。 BOUND t ) ? 算法Bubble的时间复杂性主要依赖于while语句的循环次数、关键词的比较次数和记录的交换次数。 。