冒泡排序

1. 前言

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

2. 什么是冒泡排序？

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

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

冒泡排序的算法名稱(chēng)的由來(lái)就是因?yàn)樵谂判虻倪^(guò)程中，按照排序規(guī)則（升序或者降序），越小或者越大的元素會(huì)經(jīng)過(guò)交換之后慢慢 “浮” 到序列的頂端，就如同水中的氣泡一樣最終會(huì)浮到頂端一樣，所以起名為 “冒泡排序”。

3. 冒泡排序過(guò)程

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

3.1 算法步驟

1. 步驟 1：

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

2. 步驟 2：

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

3. 步驟 3：

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

4. 步驟 4：

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

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

3.2 算法演示

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

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

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

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

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

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

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

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

在說(shuō)明冒泡排序的整個(gè)過(guò)程之后，接下來(lái)，我們看看如何用 Java 代碼實(shí)現(xiàn)冒泡排序算法。

import java.util.Arrays;

public class BubbleSort {

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

}

運(yùn)行結(jié)果如下：

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

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

5. 小結(jié)

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