冒泡排序

1. 前言

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

2. 什么是冒泡排序？

冒泡排序（Bubble Sort），是計算機科學(xué)與技術(shù)領(lǐng)域中較為簡單的一種排序算法。

它重復(fù)地遍歷要排序的序列，會依次比較兩個相鄰的元素，如果發(fā)現(xiàn)兩個相鄰的元素順序錯誤就把它們交換過來。遍歷序列的工作會重復(fù)地進行直到?jīng)]有相鄰的元素需要交換位置，也就是說序列的排序工作已經(jīng)完成。

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

3. 冒泡排序過程

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

3.1 算法步驟

1. 步驟 1：

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

2. 步驟 2：

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

3. 步驟 3：

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

4. 步驟 4：

持續(xù)以上步驟 1， 步驟 2， 步驟 3 的工作，每重復(fù)一次需要排序的序列中少一個最右邊的元素，直到?jīng)]有任何一對數(shù)字需要比較排序。

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

3.2 算法演示

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

接著，我們調(diào)用步驟 2，重復(fù)每一對的排序工作，整個過程如下：

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

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

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

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

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

4. Java 代碼實現(xiàn)

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

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        
        //初始化需要排序的數(shù)組
        int array[] = {9,2,11,7,12,5};
        
        //對需要排序的數(shù)組進行排序
        for (int i=1; i<array.length; i++){
            
            //針對待排序序列中除了已經(jīng)排序好的元素之外，重復(fù)排序工作
            for(int j=0;j<array.length-i;j++){
                
                //當(dāng)相鄰兩個元素需要交換時，交換相鄰的兩個元素
                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));
    }

}

運行結(jié)果如下：

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

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

5. 小結(jié)

本節(jié)主要學(xué)習(xí)了冒泡排序算法，在學(xué)完本節(jié)課程之后，需要熟悉冒泡排序的算法流程，知道冒泡排序算法的實現(xiàn)思路，可以自己用代碼實現(xiàn)冒泡排序算法。