() ① ②A[j]>A[j+] ③b:=true ()冒泡排序 ()次比較次交換
() n(n)/次比較n(n)/次交換(相當n(n)/次移動)本題中n=故有次比較和交換(相當次移動)
答此排序為雙向起泡排序從前向後一趟排序下來得到一個最大值若其中發生交換則再從後向前一趟排序得到一個最小值
一趟
二趟 三趟
四趟 五趟
六趟 七趟
對冒泡算法而言初始序列為反序時交換次數最多若要求從大到小排序則表現為初始是上升序
證明起泡排序思想是相鄰兩個記錄的關鍵字比較若反序則交換一趟排序完成得到一個極值由題假設知Rj在Ri之前且Kj>Ri即說明Rj和Ri是反序設對於Ri之前全部記錄Ri(其中包括Kj)中關鍵字最大為Kmax則Kmax≥Kj故經過起泡排序前i次後Ri的關鍵字一定為Kmax又因Kmax≥Kj>Ri故Ri和Ri為反序由此可知Ri和Ri必定交換證畢
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23194.html
