基本思想
冒泡排序的基本思想是:每一次将最具有特征的一個數(或者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。
産生
在許多程序設計中,我們需要将一個數列進行排序,以方便統計,常見的排序方法有冒泡排序,二叉樹排序,選擇排序等等。冒泡排序比其它排序具有簡單、容易設計的特點,在一樣對性能要求不是很高的場合下,冒泡排序得到了青睐。特别是在一些情況下,僅僅隻是要找到序列中最具有特色的一個或兩個數字是,這種法方特别實用。
算法分析
設想被排序的數組R[1..N]垂直豎立,将每個數據元素看作有重量的氣泡,根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組R,凡掃描到違反本原則的輕氣泡,就使其向上"漂浮",如此反複進行,直至最後任何兩個氣泡都是輕者在上,重者在下為止。
冒泡排序法的改進
比如用冒泡排序将4、5、7、1、2、3這6個數排序。在該列中,第二趟排序結束後,數組已排好序,但計算機此時并不知道已經反排好序,計算機還需要進行一趟比較,如果這一趟比較,未發生任何數據交換,則知道已排序好,可以不再進行比較了。因而第三趟比較還需要進行,但第四、五趟比較則是不必要的。為此,我們可以考慮程序的優化。
為了标志在比較中是否進行了,設一個布爾量flag。在進行每趟比較前将flag置成true。如果在比較中發生了數據交換,則将flag置為false,在一趟比較結束後,再判斷flag,如果它仍為true(表明在該趟比較中未發生一次數據交換)則結束排序,否則進行下一趟比較。