冒泡排序

1. 前言

本節內容是排序算法系列之一：冒泡排序，主要講解了冒泡排序的主體思路，選取了一個待排序的數字列表對冒泡排序算法進行了演示，給出了冒泡排序算法的 Java 代碼實現，幫助大家可以更好地理解冒泡排序算法。

2. 什么是冒泡排序？

冒泡排序（Bubble Sort），是計算機科學與技術領域中較為簡單的一種排序算法。

它重復地遍歷要排序的序列，會依次比較兩個相鄰的元素，如果發現兩個相鄰的元素順序錯誤就把它們交換過來。遍歷序列的工作會重復地進行直到沒有相鄰的元素需要交換位置，也就是說序列的排序工作已經完成。

冒泡排序的算法名稱的由來就是因為在排序的過程中，按照排序規則（升序或者降序），越小或者越大的元素會經過交換之后慢慢 “浮” 到序列的頂端，就如同水中的氣泡一樣最終會浮到頂端一樣，所以起名為 “冒泡排序”。

3. 冒泡排序過程

在介紹完冒泡排序之后，我們一起來看一下冒泡排序的實現步驟具體是什么樣的吧。這里我們假設待排序的序列為 [9,2,11,7,12,5]，我們按照從小到大的序列進行排序。

3.1 算法步驟

1. 步驟 1：

比較待排序序列中相鄰的兩個元素，如果發現左邊的元素比右邊的元素大，則交換這兩個元素；

2. 步驟 2：

每一對相鄰的兩個元素重復步驟 1 的動作，從左至右依次執行；

3. 步驟 3：

針對待排序序列中除了最右邊的一個元素之外，重復步驟 1， 步驟 2 的工作；

4. 步驟 4：

持續以上步驟 1， 步驟 2， 步驟 3 的工作，每重復一次需要排序的序列中少一個最右邊的元素，直到沒有任何一對數字需要比較排序。

其實，上面的步驟 2 每執行一次，都有一個排序好的數字放到需要排序的序列的最右邊，這樣一直重復，可以完成最開始的整個待排序序列的排序工作。接下來，讓我們用上面的待排序數字隊列 [9,2,11,7,12,5] 進行整個算法步驟的排序演示工作。

3.2 算法演示

按照排序步驟，首先我們會比較待排序序列中（9,2）這一對需要排序的序列，按照從小到大進行排序，需要交換位置，形成序列（2,9），如下：

接著，我們調用步驟 2，重復每一對的排序工作，整個過程如下：

步驟 2 會依次比較待排序序列中相鄰的兩個元素，按照如上過程一樣。當相鄰的兩個元素已經是排序好的時候，無需交換順序，否則交換相鄰兩個元素的順序。

Tips: 步驟 2 每執行一次都會有一個元素排序好，就是所謂的冒泡的過程，按照從小到大的順序排列時，每次都會有一個最大的元素排序好，放在待排序序列的最右邊。

完成步驟 2 之后，說明我們已經把最大的一個元素 12 排序好啦，接下來我們只需要對序列 [2,9,7,11,5] 進行排序即可，就如 步驟 3 描述一下，然后重復 步驟 1， 步驟 2 中的工作，具體過程執行如下：

我們發現當我們執行 步驟 3 之后，之前的待排序隊列 [2,9,7,11,5] 中的最大的一個元素 11 又已經排序好啦，接下來我們只需要調用 步驟 4 的工作，重復之前 步驟 1， 步驟 2， 步驟 3，這里我們就不在演示，只是重復性的進行排序工作，每執行一次 步驟 4，就已經把一個元素排序好，待排序的序列中就減少了一個序列，每次會有一個排序好的數字和一個剩下的待排序數列。其實，整個過程如下：

從上面的示例可以看出，其實整個冒泡排序的過程，每次都會把最大的一個數字排序出來，放在整個序列的最右邊，重復執行整個過程，直到整個序列中已經沒有需要排序的數值了。

4. Java 代碼實現

在說明冒泡排序的整個過程之后，接下來，我們看看如何用 Java 代碼實現冒泡排序算法。

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        
        //初始化需要排序的數組
        int array[] = {9,2,11,7,12,5};
        
        //對需要排序的數組進行排序
        for (int i=1; i<array.length; i++){
            
            //針對待排序序列中除了已經排序好的元素之外，重復排序工作
            for(int j=0;j<array.length-i;j++){
                
                //當相鄰兩個元素需要交換時，交換相鄰的兩個元素
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

運行結果如下：

[2, 5, 7, 9, 11, 12]

代碼中的第 8 行初始化一個需要排序的數組，后面按照從小到大的排序規則，實現了數組的排序。第 11 行是外層循環，不斷地重復排序工作。第 14 行是內層循環，不斷地實現每一次 “冒泡” ，將最大的一個元素找出。第 17 至第 21 行實現當相鄰兩個元素需要交換時，交換相鄰的兩個元素的功能。第 25 行打印出排序好的數組。

5. 小結

本節主要學習了冒泡排序算法，在學完本節課程之后，需要熟悉冒泡排序的算法流程，知道冒泡排序算法的實現思路，可以自己用代碼實現冒泡排序算法。