基本概念??

冒泡排序是一種簡單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，依次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

冒泡排序的思想就是每一輪把所有元素下標為01，12，23，34.....如此一直比較到n-1和n。若當前的比前一個?。ㄟ@里我們默認為從小到大的排序），那么進行調(diào)換。每一輪下來一定有一個最大的元素“冒”到最后（頂端），也就是說在最壞的情況下，最多要進行n-1次。

例如有6個元素需要排序:

653412

第一趟排序:

比較65??? ? ? 得563412? ??

比較63?? ? ? ?得536412? ? ?

比較64? ? ? ? 得534612? ??

比較61? ? ? ? 得534162? ? ?

比較62? ? ? ? 得534126? ? ?

第一趟結(jié)束，最后的6固定下來

第二趟排序：

比較53? ? ? ? 得354126

比較54? ? ? ? 得345126

比較51? ? ? ? 得341526

比較52? ? ? ? 得341256

6已經(jīng)固定所以56不比較

第二趟結(jié)束，5固定下來

第三趟排序：

比較34? ? ? ??得341256

比較41? ? ? ? 得314256

比較42? ? ? ? 得312456

5已經(jīng)固定所以45不比較

第三趟結(jié)束，4固定下來。

第四趟排序：

比較31? ? ? ? 得132456

比較32? ? ? ? 得123456

4已經(jīng)固定所以34不比較

第四趟結(jié)束，3固定下來

第五趟排序：

比較12? ? ? ? 得123456

3已經(jīng)固定所以23不比較

第五趟結(jié)束，2固定下來

1也隨之固定下來

五趟結(jié)束后，6個整數(shù)就已經(jīng)排序完成。排序過程中,大數(shù)慢慢地往后，相當于氣泡上升，所以叫冒泡排序。

歸納上述排序過程,具體實現(xiàn)步驟如下:

①讀人數(shù)據(jù)存放在a數(shù)組中。

②比較相鄰的前后兩個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù),就將兩個數(shù)據(jù)交換。

③對數(shù)組的第0個數(shù)據(jù)到n-1個數(shù)據(jù)進行一次遍歷后,最大的一個數(shù)據(jù)就“冒”到數(shù)組第n一1個位置。

④n=n一1,如果n不為0就重復(fù)前面二步,否則排序完成。

我們用動畫看一下其過程：

程序?qū)崿F(xiàn)

程序?qū)崿F(xiàn)方法:用兩層循環(huán)完成算法,外層循環(huán)i控制每輪要進行多少次的比較,第1輪比較n一1次,第2輪比較n-2....最后一輪比較1次。內(nèi)層循環(huán)j控制每輪i次比較相鄰兩個元素是否逆序,若逆序就交換這兩個元素。

具體程序如下：

在用冒泡排序的時候，我們發(fā)現(xiàn)，對于一些數(shù)據(jù)，并不一定要n-1次才可以排完。例如1 5 2 3 4 5，我們發(fā)現(xiàn)這種情況只需要一趟排序就可以將整個序列排完，若繼續(xù)下去就大大增加了程序運行的時間而且浪費空間。于是，我們可以設(shè)置一個布爾類型的變量，判斷是否有進行交換，如果沒有，說明已經(jīng)完成了排序，從而減少幾趟排序。

那我們?nèi)绾卫眠@個布爾變量呢。

舉個栗子??

1 5 2 3 4 6 7

再此，我們要先確定好這個變量是用來干嘛的，這個變量是用來看還要不要執(zhí)行。執(zhí)行條件就是假，也就是還沒有執(zhí)行完呢，終止條件就是真，也就是執(zhí)行完了呢。就以上面的例子而言，循環(huán)每次開始我們的布爾變量是true，所以該程序可以執(zhí)行，第一趟我們對數(shù)列進行了調(diào)整，變量要變成假，代表還要繼續(xù)，此時，數(shù)列已經(jīng)有序化，下一次執(zhí)行的時候并沒有對數(shù)列進行調(diào)整，所以并沒有將變量改為假，所以跳出循環(huán)，直接輸出有序數(shù)列就行了。

具體程序如下：

部分格式和代碼借鑒了《信息學(xué)奧賽一本通（C++）》

up打字不容易，思路整理更不容易，點一個免費的贊??鼓勵一下up吧！up是用手機打的字，眼睛??都要瞎了，點個贊吧不浪費你們的時間，改天up給你們表演一個猴子上樹！??