標籤: 暫無標籤

冒泡排序,是指計算機的一種排序方法,它的時間複雜度為O(n^2),有兩個優點:1.「編程複雜度」很低,很容易寫出代碼;2.具有穩定性,這裡的穩定性是指原序列中相同元素的相對順序仍然保持到排序后的序列,而堆排序、快速排序均不具有穩定性。

1 冒泡排序 -基本思想


冒泡排序的基本思想是:每一次將最具有特徵的一個數(或者object)放到序列的最前面,或者最後面。例如,如果需要將一組數,以從小到大的順序排列,那麼就可以設計這樣的冒泡方法:在每一次循環中,都將最大的一個數找出來,放在最後面,這樣設有n個數字,經過n次循環以後,整個序列就呈現出了從小到大的排列了。亦即,可以設計從序列的最後面開始,找出序列中最小的一個數放到序列的最前面,這樣經過n次循環也可以實現數組的排列。這種排序方法由於每一次找到的數字都像是氣泡一樣從數組裡冒出來而得名為「冒泡排序」。


用二重循環實現,外循環變數設為i,內循環變數設為j。外循環重複9次,內循環依次重複9,8,...,1次。每次進行比較的兩個元素都是與內循環j有關的,它們可以分別用a[j]和a[j+1]標識,i的值依次為1,2,...,9,對於每一個i, j的值依次為1,2,...10-i。

2 冒泡排序 -產生



在許多程序設計中,我們需要將一個數列進行排序,以方便統計,常見的排序方法有冒泡排序,二叉樹排序,選擇排序等等。冒泡排序比其它排序具有簡單、容易設計的特點,在一樣對性能要求不是很高的場合下,冒泡排序得到了青睞。特別是在一些情況下,僅僅只是要找到序列中最具有特色的一個或兩個數字是,這種法方特別實用。


 

3 冒泡排序 -排序過程


設想被排序的數組R[1..N]垂直豎立,將每個數據元素看作有重量的氣泡,根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組R,凡掃描到違反本原則的輕氣泡,就使其向上"漂浮",如此反覆進行,直至最後任何兩個氣泡都是輕者在上,重者在下為止。

演算法示例

49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //從下往上掃描的起泡排序//
Begin
For I := 1 To N-1 Do //做N-1趟排序//
begin
NoSwap := True; //置未排序的標誌//
For J := N - 1 DownTo 1 Do //從底部往上掃描//
begin
If R[J+1]< R[J] Then //交換元素//
begin
Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
NoSwap := False
end;
end;
If NoSwap Then Return//本趟排序中未發生交換,則終止演算法//
end
End; //BubbleSort//
該演算法的時間複雜性為O(n2),演算法為穩定的排序方

4 冒泡排序 -冒泡排序法的改進



比如用冒泡排序將4、5、7、1、2、3這6個數排序。在該列中,第二趟排序結束后,數組已排好序,但計算機此時並不知道已經反排好序,計算機還需要進行一趟比較,如果這一趟比較,未發生任何數據交換,則知道已排序好,可以不再進行比較了。因而第三趟比較還需要進行,但第四、五趟比較則是不必要的。為此,我們可以考慮程序的優化。

為了標誌在比較中是否進行了,設一個布爾量flag。在進行每趟比較前將flag置成true。如果在比較中發生了數據交換,則將flag置為false,在一趟比較結束后,再判斷flag,如果它仍為true(表明在該趟比較中未發生一次數據交換)則結束排序,否則進行下一趟比較。

上一篇[夕堂永日緒論]    下一篇 [約瑟夫環]

相關評論

同義詞:暫無同義詞