【庖丁解題】排序算法之冒泡排序剖析

轉載聲明：商業轉載請聯系作者獲得授權,非商業轉載請注明出處.原文來自 © 呆萌鐘【庖丁解題】排序算法之冒泡排序剖析

前言

排序算法一直是面試的高頻考點，但是如果沒有真正了解不同算法的原理，光靠硬背，很容易到需要用的時候就忘記了。要想靈活運用并熟記各種算法，前提是必須去了解它們。那接下來，我就帶大家抽絲剝繭，剖析那些經典算法！

冒泡排序

冒泡排序是所有排序中最常出現的，是以這篇文章我先為大家講解冒泡排序。

概述（百度百科）

它重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重複地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。

這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

算法原理

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
3. 針對所有的元素重複以上的步驟，除了最後一個。
4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

圖解

光看百度百科的解釋還是比較難以了解吧，那我們用圖形的形式來表述這個原理，相信你立馬會恍然大悟。

首先，我們準備一組需要進行排序的資料。

然後，根據上面的算法原理，我們進行第一輪比較

執行完第一輪排序之後，拿第一輪排序完之後的結果進行第二輪排序

重複上述操作，執行第三輪排序

執行第四輪

第四輪執行完畢之後，我們可以發現，所有的相鄰元素我們都比較過了一遍，而且此時第四輪的結果已經是呈現升序排序了。如果把每個元素看成一個氣泡，值越大的資料泡泡越大，并且大的泡泡都往上冒，可以了解為如下圖：

這就是冒泡排序的原理，此時在結合上面的算法原理，是不是覺得如此簡單呢？

代碼實作

好了，前面我們已經根據圖文并茂的形式了解了冒泡排序的原理，那接下來我們要做的就是如何把它轉換成代碼輸出，我這邊用Java代碼為例。

分析

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

代碼表現如下：

if (arr[i]>arr[i+1]) {//比較相鄰的元素
    //交換
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
}
           

對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對

意味着要用循環周遊去比較

for(int i=0;i<arr.length;i++){
    if (arr[i]>arr[i+1]) {//比較相鄰的元素
        //交換
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
  }
           

但是這段代碼有一個問題，當i=arr.length-1時，也可了解為比較到最後一個元素時，i+1将會等于arr.length，這會導緻arr[i+1]報數組下标越界異常，是以我們需要限定循環的範圍是小于arr.length-1，代碼辨別如下：

for(int i=0;i<arr.length-1;i++){
  if (arr[i]>arr[i+1]) {//比較相鄰的元素
      //交換
      int temp = arr[i];
      arr[i] = arr[i+1];
      arr[i+1] = temp;
  }
}
           

然而，以上代碼隻能實作第一輪排序。但是我們觀察圖解部分的每輪排序的圖檔，可以發現，我們總共進行了四輪排序，是以可以得出結論需要執行的排序輪數等于數組長度減1.

for(int k=0;k<arr.length-1;k++){//外層循環控制排序輪數
            for(int i=0;i<arr.length-1;i++){//内層循環控制每一輪的排序次數
                if (arr[i]>arr[i+1]) {//比較相鄰的元素
                    //交換
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
           

執行完上述代碼，我們會發現我們的數組已經排好序了。你以為這就萬事大吉了？NO，我們再來看看圖解部分的圖檔，可以發現，每一輪比較的次數都比上一輪少了一次。第一輪4次，第二輪3次，第三輪2次，第四輪1次。是以，我們上面的代碼雖然實作了排序，但是每次還會比較已經排好序的元素，增加了時間複雜度。是以我們應該在每輪排序的時候減去那些已經排好序的元素，隻比較未排好序的元素。經過分析，我們可以發現，第一輪排好序的元素為0個，第二輪1個，第三輪2個，第四輪3個，是以我們可以得出結論，每輪排好序的元素與輪次成正比，我們隻需要在每輪比較排序之前減去已經排好序的元素個數就可以了. 例如：

第一輪需要比較的元素個數:arr.length-0
第二輪需要比較的元素個數:arr.length-1
第三輪需要比較的元素個數:arr.length-2
第四輪需要比較的元素個數:arr.length-3
           

由此我們可以得出如下代碼

for(int k=0;k<arr.length-1;k++){//外層循環控制排序輪數
            for(int i=0;i<arr.length-1-k;i++){//内層循環控制每一輪的排序次數
                if (arr[i]>arr[i+1]) {//比較相鄰的元素
                    //交換
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }
           

以上代碼就是冒泡排序的最終實作。

總結

通過圖解加理論加推演分析，是不是覺得冒泡排序不過如此？相信你看完這篇文章，媽媽再也不用擔心我寫不出冒泡排序了~