摘要：算法思想冒泡排序屬于一種典型的交換排序。冒泡排序常規版代碼實現下面詳細分析一下常規版的冒泡排序，整個算法流程其實就是上面實例所分析的過程。

　　冒泡排序屬于一種典型的交換排序。

　　交換排序顧名思義就是通過元素的兩兩比較，判斷是否符合要求，如過不符合就交換位置來達到排序的目的。冒泡排序名字的由來就是因為在交換過程中，類似水冒泡，小（大）的元素經過不斷的交換由水底慢慢的浮到水的頂端。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　這個時候就可以看出，排序實際上在第三遍已經完成了，但是算法還是會繼續向下進行，下面就進行代碼實現，看一下究竟是什么情況。。

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

　　關于最優時間復雜度為什么是O(n)，當然是優化過算法之后了！大家繼續向下看就知道了！。

　　下面詳細分析一下常規版的冒泡排序，整個算法流程其實就是上面實例所分析的過程。可以看出，我們在進行每一次大循環的時候，還要進行一個小循環來遍歷相鄰元素并交換。所以我們的代碼中首先要有兩層循環。

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

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

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

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

　　運行結果

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

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

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

　　為了解決這個問題，我們可以設置一個標志位，用來表示當前第 i 趟是否有交換，如果有則要進行 i+1 趟，如果沒有，則說明當前數組已經完成排序。實現代碼如下：

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

　　運行結果：可以看到優化效果非常明顯，比正常情況下少了兩次的循環。

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

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

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

　　我們用剛剛優化過一次的算法，跑一下這個數組。

/**
 * @author jyroy
 * 冒泡排序優化第一版
 */
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; // 開辟一個臨時空間, 存放交換的中間值
        // 要遍歷的次數
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設置一個標志位
            //依次的比較相鄰兩個數的大小，遍歷一次后，把數組中第i小的數放在第i個位置上
            for (int j = 0; j < len-i; j++) {
                // 比較相鄰的元素，如果前面的數小于后面的數，交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發生交換，標志位置0

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

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

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

　　針對上述的問題，我們可以想到，利用一個標志位，記錄一下當前第 i 趟所交換的最后一個位置的下標，在進行第 i+1 趟的時候，只需要內循環到這個下標的位置就可以了，因為后面位置上的元素在上一趟中沒有換位，這一次也不可能會換位置了。基于這個原因，我們可以進一步優化我們的代碼。

/**
 * @author jyroy
 * 冒泡排序優化第二版
 */
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;  // 記錄最后一次交換的位置
        // 要遍歷的次數
        for (int i = 0; i < list.length-1; i++) {
            int flag = 1; //設置一個標志位
            //依次的比較相鄰兩個數的大小，遍歷一次后，把數組中第i小的數放在第i個位置上
            for (int j = 0; j < len; j++) {
                // 比較相鄰的元素，如果前面的數小于后面的數，交換
                if (list[j] < list[j+1]) {
                    temp = list[j+1];
                    list[j+1] = list[j];
                    list[j] = temp;
                    flag = 0;  //發生交換，標志位置0
                    tempPostion = j;  //記錄交換的位置
                }
                System.out.format("第 %d 遍第%d 趟結果：", i+1, j+1);
                for(int count:list) {
                    System.out.print(count);
                }
                System.out.println("");     
            }
            len = tempPostion; //把最后一次交換的位置給len，來縮減內循環的次數
            System.out.format("第 %d 遍最終結果：", i+1);
            for(int count:list) {
                System.out.print(count);
            }
            System.out.println("");     
            if (flag == 1) {//如果沒有交換過元素，則已經有序
                return;
            }
                   
        }
    }
}

　　運行結果：

　　可以清楚的看到，部分內循環多余的比較已經被去掉了，算法得到了進一步的優化

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