问题 单项选择题

对n个不同的排序码的元素进行冒泡排序,在 (45) 情况下比较的次数最少,其比较次数为 (46) 。在 (47) 情况下比较次数最多,其比较次数为 (48)

(48)处填()。

A.n+1

B.n

C.n-1

D.

答案

参考答案:D

解析:

根据冒泡排序的思想,依次比较两个相邻关键字Ki和Ki+1(I=1, 2,…,n-1)。若Ki>Ki+1,则交换相应的元素Ri和 Ri+1;否则,不进行交换。经过这样一趟处理之后,其中关键字最大的纪录移到了第n个位置上,然后对前面n-1个纪录进行第2趟排序。重复上述处理过程,

根据上述“发现逆序则交换”的思想,可在算法中引起交换标志swap。进行第j遍之前,置swap为0,若进行交换,则置swap为1。若某一遍swap=0未发生变化,则说明元素已经是有序的,可不再进行比较。因此,当元素已是由小到大的顺序排列时,swap=0未变化,则算法即可结束。

由此可见,在从小到大排列好的情况下其比较次数最少。若要求从大到小排列,则情况正好相反。

单项选择题
填空题