算法分析
()算法的最好時間復雜度
若文件的初始狀態是正序的一趟掃描即可完成排序所需的關鍵字比較次數C和記錄移動次數M均達到最小值
C min =n
M min =
冒泡排序最好的時間復雜度為O(n)
()算法的最壞時間復雜度
若初始文件是反序的需要進行n趟排序每趟排序要進行ni次關鍵字的比較(≤i≤n)且每次比較都必須移動記錄三次
來達到交換記錄位置在這種情況下比較和移動次數均達到最大值
C max =n(n)/=O(n )
M max =n(n)/=O(n )
冒泡排序的最壞時間復雜度為O(n )
()算法的平均時間復雜度為O(n )
雖然冒泡排序不一定要進行n趟但由於它的記錄移動次數較多故平均時間性能比直接插入排序要差得多
()算法穩定性
冒泡排序是就地排序且它是穩定的
算法改進
上述的冒泡排序還可做如下的改進
()記住最後一次交換發生位置lastExchange的冒泡排序
在每趟掃描中記住最後一次交換發生的位置lastExchange(該位置之前的相鄰記錄均已有序)下一趟排序開始時
R[lastExchange]是有序區R[lastExchangen]是無序區這樣一趟排序可能使當前有序區擴充多個記錄從而減少排
序的趟數具體算法【參見習題】
() 改變掃描方向的冒泡排序
①冒泡排序的不對稱性
能一趟掃描完成排序的情況
只有最輕的氣泡位於R[n]的位置其余的氣泡均已排好序那麼也只需一趟掃描就可以完成排序
【例】對初始關鍵字序列就僅需一趟掃描
需要n趟掃描完成排序情況
當只有最重的氣泡位於R[]的位置其余的氣泡均已排好序時則仍需做n趟掃描才能完成排序
【例】對初始關鍵字序列就需七趟掃描
②造成不對稱性的原因
每趟掃描僅能使最重氣泡下沉一個位置因此使位於頂端的最重氣泡下沉到底部時需做n趟掃描
③改進不對稱性的方法
在排序過程中交替改變掃描方向可改進不對稱性具體算法【參見習題】
From:http://tw.wingwit.com/Article/program/sjjg/201311/23796.html
