Question

把由m个数据组成的无序列用冒泡排序法排成有序列，最多需要经过（　　）趟排序过程．

• A．

  m

  2

• B．m-1
• C．m
• D．2m

Answer 1

分析：依次比较相邻的两个数，将小数放在前面，大数放在后面．即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后．然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后．至此第一趟结束，将最大的数放到了最后．在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）．如此下去，重复以上过程，直至最终完成排序．

解答：解：把由m个数据组成的无序列用冒泡排序法排成有序列，按要求从大到小或从小到大排序．
方法是：对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序（与欲排顺序相反），若逆序就交换这两元素，经过第一轮比较排序后便可把最大（或最小）的元素排好，然后再用同样的方法把剩下的元素逐个进行比较，就得到了你所要的顺序．可以看出如果有 n 个元素，那么一共要进行 n-1 趟比较，第 i 轮要进行 j=n-i 次比较．
如：有5个元素，则要进行5-1轮比较．
故把由m个数据组成的无序列用冒泡排序法排成有序列，最多需要经过m-1趟排序过程．
故选B．

点评：本题主要考查了冒泡排序法．由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序．