熱心網(wǎng)友

9。2。1 冒泡排序 把記錄序列圖示成上下（或左右）次序，如右圖，記錄R1,R2,…,Rn序列為自下而上排列（即R1在最下面，Rn在最上面）。記錄交換的方法是自下而上（或從左到右）比較相鄰記錄的關鍵詞Kj和Kj+1 ．若Kj＞Kj+1，則互換Rj和Rj+1 ．這樣，進行一趟比較，我們至少把具有最大關鍵詞的記錄送到最上邊（或最右邊，相應右圖所示的“——”線），因此下一趟的比較次數(shù)將至少減少一次 。 算法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 ) ?算法中關鍵詞的比較次數(shù)為 可以減少算法中的關鍵詞的比較次數(shù)嗎？ 我們對如下9個元素執(zhí)行冒泡排序： 07 09 02 16 08 05 12 13 14算法執(zhí)行完第一次冒泡過程之后，記錄序列變成如下：07 02 09 08 05 12 13 14 16按照算法BSort，下一次冒泡操作從第一個元素到第八個元素，記錄序列變成如下：02 07 08 05 09 12 13 14 16最后一次記錄交換發(fā)生在第四和第五個元素之間，事實上，下一次冒泡過程我們不必要從第一個元素檢查到第七個元素，因為從第五個元素之后的所有元素已經(jīng)排序完畢，因此下一次的冒泡循環(huán)到第四個元素就可以結束了，這樣可以減少算法的關鍵詞比較次數(shù)。 因此可以得出結論：在每一趟的比較中，當比較結束后，如果發(fā)現(xiàn)從某個位置t開始，不再進行記錄交換，即說明從Rt+1～Rn已經(jīng)排序（證明留作練習），從而下一趟的比較只要進行到位置t即可。據(jù)此我們可以給出一種改進的冒泡排序算法。 算法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語句的循環(huán)次數(shù)、關鍵詞的比較次數(shù)和記錄的交換次數(shù)。 。