Question

把由m個(gè)數(shù)據(jù)組成的無序列用冒泡排序法排成有序列，最多需要經(jīng)過（　�。┨伺判蜻^程．

• A．

  m

  2

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

Answer 1

分析：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面．即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后．然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后．至此第一趟結(jié)束，將最大的數(shù)放到了最后．在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）．如此下去，重復(fù)以上過程，直至最終完成排序．

解答：解：把由m個(gè)數(shù)據(jù)組成的無序列用冒泡排序法排成有序列，按要求從大到小或從小到大排序．
方法是：對(duì)尚未排序的各元素從頭到尾依次比較相鄰的兩個(gè)元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經(jīng)過第一輪比較排序后便可把最大（或最小）的元素排好，然后再用同樣的方法把剩下的元素逐個(gè)進(jìn)行比較，就得到了你所要的順序．可以看出如果有 n 個(gè)元素，那么一共要進(jìn)行 n-1 趟比較，第 i 輪要進(jìn)行 j=n-i 次比較．
如：有5個(gè)元素，則要進(jìn)行5-1輪比較．
故把由m個(gè)數(shù)據(jù)組成的無序列用冒泡排序法排成有序列，最多需要經(jīng)過m-1趟排序過程．
故選B．

點(diǎn)評(píng)：本題主要考查了冒泡排序法．由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當(dāng)于氣泡往上升，所以稱作冒泡排序．