引入??

今天，我們來學習一種排序算法——冒泡排序。

首先，先問三個問題：

1.為什么要排序？??

想象一下，如果字典不是按照字母順序排列，查找一個單詞，你得查到什么時候？這就是為什么人們引入了分類的概念，因為其極大地幫助我們快速搜索物品。

或者說，排序是一種常用的整理信息的方法。排序可克服資料混亂、不便交流、查閱困難、挑選或取舍困難、不便安排等等問題。

2.有那些常用的排序算法？?

冒泡排序、選擇排序、插入排序、歸并排序等等都是常用的排序算法。

各種排序的復雜度、方式等方面都略有不同，下面這張圖可以反映（圖片參考自常用十大排序算法）：

3.什么是冒泡排序？??

冒泡排序（Bubble Sort），是一種 計算機科學領域的較簡單的 排序算法。
它重復地走訪過要排序的元素列，依次比較兩個相鄰的 元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復地進行，直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。
這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中 二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

這是百度的說法，讓我們來看看另一種說法。

冒泡排序就是重復“從序列右邊開始比較相鄰兩個數(shù)字的大小，再根據(jù)結(jié)果交換兩個數(shù)字的位置”這一操作的算法。在這個過程中，數(shù)字會像泡泡一樣，慢慢從右往左“浮”到序列的頂端，所以這個算法才被稱為“冒泡排序”。

來自《我的第一本算法書》。

總的來說，就是一句話：

通過不斷比較相鄰元素，將大的元素放到數(shù)組后面，最終完成排序。

這具體是什么原理呢？請看下面。

---

原理?

文字解釋??

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2. 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。

3. 針對所有的元素重復以上的步驟，除了最后一個。

4. 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

舉個栗子（文字說明）??

對6 3 2 5 4 1 這個亂序數(shù)字串進行冒泡排序。

第一步.3 2 5 4 1 6

第二步.2 3 4 1 5 6

第三步.2 3 1 4 5 6

第四步.2 1 3 4 5 6

第五步.1 2 3 4 5 6

這樣就完成了。

舉個栗子（圖文混合說明）??

注：此處與上面的排序不太一樣，上面是把大的優(yōu)先放在后面，這是把小的依次放到前面。

在序列的最右邊放置一個天平，比較天平兩邊的數(shù)字。如果右邊的數(shù)字較小，就交換這兩個數(shù)字的位置。

由于6＜7，所以交換這兩個數(shù)字。

完成后，天平往左移動一個位置，比較兩個數(shù) 字的大小。此處4＜6，所以無須交換。

繼續(xù)將天平往左移動一個位置并比較數(shù)字。重復同樣的操作直到天平到達序列最左邊為止。

不斷對數(shù)字進行交換，天平最終到達了最左邊。通過這一系列操作，序列中最小的數(shù)字就會移動到最左邊。

最左邊的數(shù)字已經(jīng)歸位

將天平移回最右邊，然后重復之前的操作，直到天平到達左邊第2個位置為止

當天平到達左邊第2個位置時，序列中第2小的數(shù)字也就到達了指定位置。

將天平再次移回最右邊，重復同樣的操作直到所有數(shù)字都歸位為止

排序中…

排序完成。

---

一些說明??

時間復雜度

在冒泡排序中，第 1 輪需要比較 n -1 次，第 2 輪需要比較 n -2 次……第 n -1 輪需 要比較 1 次。因此，總的比較次數(shù)為 (n -1) +(n -2) +…+1 ≈ (n^2)/2。這個比較次數(shù)恒定為該數(shù)值，和輸入數(shù)據(jù)的排列順序無關。

不過，交換數(shù)字的次數(shù)和輸入數(shù)據(jù)的排列順序有關。假設出現(xiàn)某種極端情況，如輸 入數(shù)據(jù)正好以從小到大的順序排列，那么便不需要任何交換操作；反過來，輸入數(shù)據(jù)要 是以從大到小的順序排列，那么每次比較數(shù)字后便都要進行交換。因此，冒泡排序的時間復雜度為 O(n^2 )。

兩種不同的比較方法

相信大家都注意到了，文字說明與圖文混合說明比較順序是不同的。一個是把最大，第二大，第三大，...第n大依次放到后面；一個是把最小，第二小，...，第n小依次冒到前面。

不過，它們都是冒泡排序！

---

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

注：此處用的是把最大，第二大，第三大，...第n大依次放到后面的冒泡順序。

步驟圖

代碼??

不用說了，很簡單。（只插入中心部分）

    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
            }
        }
    }

---

優(yōu)化??

問題

數(shù)據(jù)的順序排好之后，冒泡算法仍然會繼續(xù)進行下一輪的比較。很顯然，后面的比較沒有意義的。

解決辦法??

設置bool變量flag（用于標記），如果發(fā)生了交換flag設置為true；如果沒有交換就設置為false。

這樣當一輪比較結(jié)束后如果flag仍為false，即：這一輪沒有發(fā)生交換，說明數(shù)據(jù)的順序已經(jīng)排好，沒有必要繼續(xù)進行下去。那么，就可以結(jié)束排序了。

---

最終代碼??

    bool b;
    for(int i=n;i>=1;i--)
    {
        b=false;
        for(int j=1;j<i;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                b=true;
            }
        }
        if(b==false) break;
    }

---

結(jié)語

冒泡很簡單，但是排序算法的基礎。必須學會！文章來源地址http://www.zghlxwxcb.cn/news/detail-602463.html