摘要：經過一次冒泡排序，最終在無序表中找到一個最大值，第一次冒泡結束。也是我們后面要說的冒泡排序的優化。冒泡排序只執行第一層循環，而不會執行第二層循環。因此冒泡排序的時間復雜度是。

冒泡排序（Bubble Sorting），是一種計算機科學領域的較簡單的排序算法。它的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）, 依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。故名“冒泡排序”。

我們先通過圖來簡單理解一下一次冒泡的過程

圖中可以看出，經過一次冒泡，9這個當前數組中最大的元素飄到了最上面，如果進行N次這樣操作，那么數組中所有元素也就到飄到了它本身該在的位置，就像水泡從水中飄上來，所以叫冒泡排序。

具體實現過程：

首先 9 和 2 比較，由于 9 > 2，所以兩者交換位置，即從A[0]到A[1]的轉變。

然后繼續下標為 1 的同下標為 2 的進行比較，由于 9 > 7，所以繼續進行位置移動。

直至 A[4]，9 和 3 進行比較，繼續發生位置交換；

在比較的過程中，找到最大的某一個數，并進行移動。經過一次冒泡排序，最終在無序表中找到一個最大值 9，第一次冒泡結束。

看下整個冒泡過程

從圖中我們可以看到，在第三次冒泡的時候，就已經達到了有序狀態。因此我們可以做一個標識，當冒泡操作沒有進行數據交換時，就可以認為已經達到了有序狀態。也是我們后面要說的冒泡排序的優化。

通過圖片理解完冒泡排序整個過程后，我們開始準備些冒泡排序的算法了。

在寫算法之前，我們先用最笨的辦法，把冒泡排序手寫一遍，總結下其中的規律在哪？

從上圖整個冒泡排序過程，我們可以小結一下：

(1)一共進行數組的大小-1 次大的循環
(2)每一趟排序的次數在逐漸的減少
(3)在冒泡排序中，沒有發生一次交換，可以提前結束冒泡排序。這個就是優化

口訣

外層循環 0到n-1 //控制比較輪數 n 表示元素的個數

內層循環 0到n-i-1 //控制每一輪比較次數

兩兩比較做交換

/**
 * @author: Coder編程
 * @create: 2019-6-18 21:31
 * @description: 冒泡排序
 **/
 
public class BubbleSort {


    public Integer[] bubbleSort(Integer[] arr) {
        //如果只有一個元素就不用排序了
        if (arr.length <= 1) return arr;
 
        for (int i = 0; i < arr.length; ++i) {
            // 提前退出冒泡循環的標志位,即一次比較中沒有交換任何元素，這個數組就已經是有序的了
            boolean flag = false;
            for (int j = 0; j < arr.length - i - 1; ++j) {        //此處的 arr.length - i - 1就是每趟排序的減少
                // 數組下標又是從0開始的，i下標后面已經排序的個數就得多減1，總結就是i增多少，j的循環位置減多少
                if (arr[j] > arr[j + 1]) {        //前一位與后一位與前一位比較，如果前一位比后一位要大，那么交換
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            //沒有數據交換，數組已經有序，退出排序
            if (!flag) break;
        }
        return arr;
    }
 
    public static void main(String[] args) {
        Integer arrays[] = {2,9,7,5,3};
        System.out.print("歡迎個人公眾號Coder編程：冒泡排序前：");
        Arrays.asList(arrays).stream().forEach(x -> System.out.print(x + " "));

        BubbleSort bubbleSort = new BubbleSort();
        Integer[] result = bubbleSort.bubbleSort(arrays);

        System.out.print("
歡迎個人公眾號Coder編程：冒泡排序后：");
        Arrays.asList(result).stream().forEach(x -> System.out.print(x + " "));
    }

輸出結果：

上面的代碼已經進行過優化，加了排序中，沒有發生一次交換，提前結束冒泡排序的標識flag。

這里推薦另外一種優化方式：雞尾酒排序，也叫雙向冒泡排序。

public static Integer[] sort(Integer[] arr){
    //依次將最大的數放置到數組末尾，將第二大的數放到倒數第二位...
    boolean changed;
    for(int i = 0;i < arr.length/2;i++){
        changed = false;
        //從前往后,比較相鄰兩個數,把大的放在后邊.之前已放置成功的可以不再參與比較
        for(int j = i;j < arr.length-1-i;j++){

            if(arr[j]>arr[j+1]) {
                swap(arr,j,j+1);
                changed =true;
            }
        }
        if(!changed){
            break;
        }
        for(int j = arr.length-1-i; j > i; j--){

            if(arr[j]
5. 冒泡排序性能分析
對于時間復雜度與空間復雜度概念不太了解的朋友可以看我寫的上一篇文章： 數據結構與算法（一）：帶你了解時間復雜度和空間復雜度到底是什么？
5.1 最劣的情況 O(n^2)
計算最糟糕情況，就是全部逆序情況。時間復雜度為O(n^2)
比較次數和移動次數分別為n(n-1)/2和3n(n-1)/2

我們以比較次數進行理解
冒泡排序一共要進行(n-1)次循環,每一次循環都要進行當前n-1次比較。所以一共的比較次數是: 
(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2; 
因此冒泡排序的時間復雜度是 O(n2)。
移動次數很好理解。會發生3次交換，因此常量系數為3。
5.1 最優的情況 O(n)
計算優情況時，也就是全部是順序的情況下。冒泡排序只執行第一層for循環，而不會執行第二層for循環。
因此冒泡排序的時間復雜度是 O(n)。
6. 冒泡排序擴展閱讀
6.1 C語言版
void bubble ( int arr[], int n)
{
    int i;
    int temp;
    for (i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
}

void bubbleSort ( int arr[], int n)
{
    int i;
    for (i = n; i >= 1; i--) {
        bubble(arr, i);
    }
}

6.2 Python版
def sort_myarr():
    myarr=[2,9,7,5,3]
    lenth=len(myarr)
    for i in range(lenth):
        for j in range(lenth-i-1):
            if myarr[j]>myarr[j+1]:
                temp=myarr[j]
                myarr[j]=myarr[j+1]
                myarr[j + 1]=temp

    print(myarr)

6.3 JS版
var examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
    for(i=0;iarr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
sortarr(examplearr);
console.log(examplearr);

6. 冒泡排序總結
優點： 比較簡單，空間復雜度較低，是穩定的。
缺點： 時間復雜度太高，效率不好。
其他可看上面的小結與算法口訣。
參考文章
https://cloud.tencent.com/dev...
http://www.pianshen.com/artic...
https://blog.csdn.net/Hydra_s...
文末
歡迎關注個人微信公眾號：Coder編程
獲取最新原創技術文章和免費學習資料，更有大量精品思維導圖、面試資料、PMP備考資料等你來領，方便你隨時隨地學習技術知識！
新建了一下qq群：315211365，歡迎大家進群交流一起學習。謝謝了！也可以介紹給身邊有需要的朋友。
文章收錄至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...