摘要：算法思想冒泡排序?qū)儆谝环N典型的交換排序。冒泡排序常規(guī)版代碼實現(xiàn)下面詳細(xì)分析一下常規(guī)版的冒泡排序，整個算法流程其實就是上面實例所分析的過程。

　　冒泡排序?qū)儆谝环N典型的交換排序。

　　交換排序顧名思義就是通過元素的兩兩比較，判斷是否符合要求，如過不符合就交換位置來達到排序的目的。冒泡排序名字的由來就是因為在交換過程中，類似水冒泡，?。ù螅┑脑亟?jīng)過不斷的交換由水底慢慢的浮到水的頂端。

　　冒泡排序的思想就是利用的比較交換，利用循環(huán)將第 i 小或者大的元素歸位，歸位操作利用的是對 n 個元素中相鄰的兩個進行比較，如果順序正確就不交換，如果順序錯誤就進行位置的交換。通過重復(fù)的循環(huán)訪問數(shù)組，直到?jīng)]有可以交換的元素，那么整個排序就已經(jīng)完成了。

　　我們通過一個示例來理解一下基本的冒泡排序，假設(shè)當(dāng)前我們有一個數(shù)組 a，內(nèi)部元素為 3，4，1，5，2，即初始狀態(tài)，如下圖所示。我們的目的就是通過 n 趟比較來實現(xiàn)有底向上從大到小的的順序。

　　我們首先進行第一遍排序，如下圖所示，紅色代表當(dāng)前比較的元素，綠色代表已經(jīng)歸位的元素。

　?。?）比較第一個和第二個元素，4>3，交換。

　?。?）比較第二個和第三個元素，1<3，不交換。

　?。?）比較第三個和第四個元素，5>1，交換。

　?。?）比較第四個和第五個元素，2>1，交換。

　　最后，我們可以看到 1 已經(jīng)位于最頂部。第一遍需要盡心四次比較才能把五個數(shù)比較完。

　　第二遍排序的初始狀態(tài)是第一遍排序的最終狀態(tài)，即4，3，5，2，1。

　?。?）比較第一個和第二個元素，3<4，不交換。

　?。?）比較第二個和第三個元素，5>3，交換。

　?。?）比較第三個和第四個元素，2<3，不交換。

　　第二遍排序，會讓 2 歸位，并且這一遍只用進行三次比較就可以了。

　　第三遍排序的初始狀態(tài)是第二遍排序的最終狀態(tài)，即4，5，3，2，1。

　?。?）比較第一個和第二個元素，5>4，交換。

　?。?）比較第二個和第三個元素，3<4，不交換。

　　第三遍排序，會讓 3 歸位，并且這一遍只用進行兩次比較就可以了。

　　然而我們可以看到這一次五個數(shù)已經(jīng)全部完成了歸位，但是當(dāng)我們采用普通的冒泡排序的時候，算法仍然會繼續(xù)向下進行。

　　第四遍排序的初始狀態(tài)是第三遍排序的最終狀態(tài)，即5，4，3，2，1。

　　這個時候就可以看出，排序?qū)嶋H上在第三遍已經(jīng)完成了，但是算法還是會繼續(xù)向下進行，下面就進行代碼實現(xiàn)，看一下究竟是什么情況。。

　　關(guān)于穩(wěn)定性：因為在比較的過程中，當(dāng)兩個相同大小的元素相鄰，只比較大或者小，所以相等的時候是不會交換位置的。而當(dāng)兩個相等元素離著比較遠(yuǎn)的時候，也只是會把他們交換到相鄰的位置。他們的位置前后關(guān)系不會發(fā)生任何變化，所以算法是穩(wěn)定的。

　　關(guān)于最優(yōu)時間復(fù)雜度為什么是O(n)，當(dāng)然是優(yōu)化過算法之后了！大家繼續(xù)向下看就知道了！。

　　下面詳細(xì)分析一下常規(guī)版的冒泡排序，整個算法流程其實就是上面實例所分析的過程?？梢钥闯?，我們在進行每一次大循環(huán)的時候，還要進行一個小循環(huán)來遍歷相鄰元素并交換。所以我們的代碼中首先要有兩層循環(huán)。

　　外層循環(huán)：即主循環(huán)，需要輔助我們找到當(dāng)前第 i 小的元素來讓它歸位。所以我們會一直遍歷 n-2 次，這樣可以保證前 n-1 個元素都在正確的位置上，那么最后一個也可以落在正確的位置上了。

　　內(nèi)層循環(huán)：即副循環(huán)，需要輔助我們進行相鄰元素之間的比較和換位，把大的或者小的浮到水面上。所以我們會一直遍歷 n-1-i 次這樣可以保證沒有歸位的盡量歸位，而歸位的就不用再比較了。

　　而上面的問題，出現(xiàn)的原因也來源于這兩次無腦的循環(huán)，正是因為循環(huán)不顧一切的向下執(zhí)行，所以會導(dǎo)致在一些特殊情況下得多余。例如 5，4，3，1，2 的情況下，常規(guī)版會進行四次循環(huán)，但實際上第一次就已經(jīng)完成排序了。

/**
 * @author jyroy
 * 冒泡排序常規(guī)版
 */
public class BubbleSortNormal {
    public static void main(String[] args) {
        int[] list = {3,4,1,5,2};
        int temp = 0; // 開辟一個臨時空間, 存放交換的中間值
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            System.out.format("第 %d 遍：
", i+1);
            //依次的比較相鄰兩個數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個位置上
            for (int j = 0; j < list.length-1-i; j++) {
                // 比較相鄰的元素，如果前面的數(shù)小于后面的數(shù)，就交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                }
                System.out.format("第 %d 遍的第%d 次交換：", i+1,j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");
            }
            System.out.format("第 %d 遍最終結(jié)果：", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("
#########################");
        }
    }
}

　　運行結(jié)果

　　經(jīng)過了上述的討論和編碼，常規(guī)的冒泡排序已經(jīng)被我們實現(xiàn)了。那么接下來我們要討論的就是剛剛分析時候提出的問題。

　　首先針對第一個問題，當(dāng)我們進行完第三遍的時候，實際上整個排序都已經(jīng)完成了，但是常規(guī)版還是會繼續(xù)排序。

　　可能在上面這個示例下，可能看不出來效果，但是當(dāng)數(shù)組是，5，4，3，1，2 的時候的時候就非常明顯了，實際上在第一次循環(huán)的時候整個數(shù)組就已經(jīng)完成排序，但是常規(guī)版的算法仍然會繼續(xù)后面的流程，這就是多余的了。

　　為了解決這個問題，我們可以設(shè)置一個標(biāo)志位，用來表示當(dāng)前第 i 趟是否有交換，如果有則要進行 i+1 趟，如果沒有，則說明當(dāng)前數(shù)組已經(jīng)完成排序。實現(xiàn)代碼如下：

/**
 * @author jyroy
 * 冒泡排序優(yōu)化第一版
 */
public class BubbleSoerOpt1 {
    public static void main(String[] args) {
        int[] list = {5,4,3,1,2};
        int temp = 0; // 開辟一個臨時空間, 存放交換的中間值
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設(shè)置一個標(biāo)志位
            //依次的比較相鄰兩個數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個位置上
            for (int j = 0; j < list.length-1-i; j++) {
                // 比較相鄰的元素，如果前面的數(shù)小于后面的數(shù)，交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發(fā)生交換，標(biāo)志位置0
                }
            }
            System.out.format("第 %d 遍最終結(jié)果：", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒有交換過元素，則已經(jīng)有序
                return;
            }
                   
        }
    }
}

　　運行結(jié)果：可以看到優(yōu)化效果非常明顯，比正常情況下少了兩次的循環(huán)。

　 這個時候我們就來討論一下上面留下的一個小地方！沒錯就是最優(yōu)時間復(fù)雜度為O(n)的問題，我們在進行了這一次算法優(yōu)化之后，就可以做到了。

　　當(dāng)給我們一個數(shù)列，5，4，3，2，1，讓我們從大到小排序。沒錯，這是已經(jīng)排好序的啊，也就是說因為標(biāo)志位的存在，上面的循環(huán)只會進行一遍，flag沒有變成1，整個算法就結(jié)束了，這也就是 O(n) 的來歷了！

　　　除了上面這個問題，在冒泡排序中還有一個問題存在，就是第 i 趟排的第 i 小或者大的元素已經(jīng)在第 i 位上了，甚至可能第 i-1 位也已經(jīng)歸位了，那么在內(nèi)層循環(huán)的時候，有這種情況出現(xiàn)就會導(dǎo)致多余的比較出現(xiàn)。例如：6，4，7，5，1，3，2，當(dāng)我們進行第一次排序的時候，結(jié)果為6，7，5，4，3，2，1，實際上后面有很多次交換比較都是多余的，因為沒有產(chǎn)生交換操作。

　　我們用剛剛優(yōu)化過一次的算法，跑一下這個數(shù)組。

/**
 * @author jyroy
 * 冒泡排序優(yōu)化第一版
 */
public class BubbleSoerOpt1 {
    public static void main(String[] args) {
        int[] list = {6,4,7,5,1,3,2};
        int len = list.length-1;
        int temp = 0; // 開辟一個臨時空間, 存放交換的中間值
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設(shè)置一個標(biāo)志位
            //依次的比較相鄰兩個數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個位置上
            for (int j = 0; j < len-i; j++) {
                // 比較相鄰的元素，如果前面的數(shù)小于后面的數(shù)，交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發(fā)生交換，標(biāo)志位置0

                }
                System.out.format("第 %d 遍第%d 趟結(jié)果：", i+1, j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");     
            }

            System.out.format("第 %d 遍最終結(jié)果：", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒有交換過元素，則已經(jīng)有序
                return;
            }
                   
        }
    }
}

　　運行結(jié)果：可以看出，第三趟的多次比較實際上可以沒有，因為中間幾個位置在第二趟就沒有過交換。

　　針對上述的問題，我們可以想到，利用一個標(biāo)志位，記錄一下當(dāng)前第 i 趟所交換的最后一個位置的下標(biāo)，在進行第 i+1 趟的時候，只需要內(nèi)循環(huán)到這個下標(biāo)的位置就可以了，因為后面位置上的元素在上一趟中沒有換位，這一次也不可能會換位置了?；谶@個原因，我們可以進一步優(yōu)化我們的代碼。

/**
 * @author jyroy
 * 冒泡排序優(yōu)化第二版
 */
public class BubbleSoerOpt2 {
    public static void main(String[] args) {
        int[] list = {6,4,7,5,1,3,2};
        int len = list.length-1;
        int temp = 0; // 開辟一個臨時空間, 存放交換的中間值
        int tempPostion = 0;  // 記錄最后一次交換的位置
        // 要遍歷的次數(shù)
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設(shè)置一個標(biāo)志位
            //依次的比較相鄰兩個數(shù)的大小，遍歷一次后，把數(shù)組中第i小的數(shù)放在第i個位置上
            for (int j = 0; j < len; j++) {
                // 比較相鄰的元素，如果前面的數(shù)小于后面的數(shù)，交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發(fā)生交換，標(biāo)志位置0
                    tempPostion = j;  //記錄交換的位置
                }
                System.out.format("第 %d 遍第%d 趟結(jié)果：", i+1, j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");     
            }
            len = tempPostion; //把最后一次交換的位置給len，來縮減內(nèi)循環(huán)的次數(shù)
            System.out.format("第 %d 遍最終結(jié)果：", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒有交換過元素，則已經(jīng)有序
                return;
            }
                   
        }
    }
}

　　運行結(jié)果：

　　可以清楚的看到，部分內(nèi)循環(huán)多余的比較已經(jīng)被去掉了，算法得到了進一步的優(yōu)化

　　因為水平有限，所以對算法的描述和分析存在一些缺陷，而且選取的例子可能有些不恰當(dāng)，大家可以多試一些數(shù)列。