Question

用冒泡排序法將下列各數排成一列：8，6，3，18，21，67，54.并寫出各趟的最后結果及各趟完成交換的次數.

 

Answer 1

【答案】

見解析。

【解析】

試題分析：每一趟都從頭開始，兩個兩個地比較，若前者小，則兩數位置不變；否則，調整這兩個數的位置.

解：第一趟的結果是：

6  3  8  18  21  54  67

完成3次交換.

第二趟的結果是：

3  6  8  18  21  54  67

完成1次交換.

第三趟交換次數為0，說明已排好次序，

即3  6  8  18  21  54  67.

考點：本題主要考查算法案例中的冒泡排序法。

點評：冒泡排序的基本概念是：依次比較相鄰的兩個數，將小數放在前面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續，直至比較最后兩個數，將小 數放前，大數放后。至此第一趟結束，將最大的數放到了最后。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小 于第2個數），將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其 實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。