摘要：經(jīng)過一次冒泡排序，最終在無序表中找到一個(gè)最大值，第一次冒泡結(jié)束。也是我們后面要說的冒泡排序的優(yōu)化。冒泡排序只執(zhí)行第一層循環(huán)，而不會(huì)執(zhí)行第二層循環(huán)。因此冒泡排序的時(shí)間復(fù)雜度是。

冒泡排序（Bubble Sorting），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。它的基本思想是：通過對(duì)待排序序列從前向后（從下標(biāo)較小的元素開始）, 依次比較相鄰元素的值，若發(fā)現(xiàn)逆序則交換，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。故名“冒泡排序”。

我們先通過圖來簡(jiǎn)單理解一下一次冒泡的過程

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

具體實(shí)現(xiàn)過程：

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

然后繼續(xù)下標(biāo)為 1 的同下標(biāo)為 2 的進(jìn)行比較，由于 9 > 7，所以繼續(xù)進(jìn)行位置移動(dòng)。

直至 A[4]，9 和 3 進(jìn)行比較，繼續(xù)發(fā)生位置交換；

在比較的過程中，找到最大的某一個(gè)數(shù)，并進(jìn)行移動(dòng)。經(jīng)過一次冒泡排序，最終在無序表中找到一個(gè)最大值 9，第一次冒泡結(jié)束。

看下整個(gè)冒泡過程

從圖中我們可以看到，在第三次冒泡的時(shí)候，就已經(jīng)達(dá)到了有序狀態(tài)。因此我們可以做一個(gè)標(biāo)識(shí)，當(dāng)冒泡操作沒有進(jìn)行數(shù)據(jù)交換時(shí)，就可以認(rèn)為已經(jīng)達(dá)到了有序狀態(tài)。也是我們后面要說的冒泡排序的優(yōu)化。

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

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

從上圖整個(gè)冒泡排序過程，我們可以小結(jié)一下：

(1)一共進(jìn)行數(shù)組的大小-1 次大的循環(huán)
(2)每一趟排序的次數(shù)在逐漸的減少
(3)在冒泡排序中，沒有發(fā)生一次交換，可以提前結(jié)束冒泡排序。這個(gè)就是優(yōu)化

口訣

外層循環(huán) 0到n-1 //控制比較輪數(shù) n 表示元素的個(gè)數(shù)

內(nèi)層循環(huán) 0到n-i-1 //控制每一輪比較次數(shù)

兩兩比較做交換

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


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

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

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

輸出結(jié)果：

上面的代碼已經(jīng)進(jìn)行過優(yōu)化，加了排序中，沒有發(fā)生一次交換，提前結(jié)束冒泡排序的標(biāo)識(shí)flag。

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

public static Integer[] sort(Integer[] arr){
    //依次將最大的數(shù)放置到數(shù)組末尾，將第二大的數(shù)放到倒數(shù)第二位...
    boolean changed;
    for(int i = 0;i < arr.length/2;i++){
        changed = false;
        //從前往后,比較相鄰兩個(gè)數(shù),把大的放在后邊.之前已放置成功的可以不再參與比較
        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. 冒泡排序性能分析
對(duì)于時(shí)間復(fù)雜度與空間復(fù)雜度概念不太了解的朋友可以看我寫的上一篇文章： 數(shù)據(jù)結(jié)構(gòu)與算法（一）：帶你了解時(shí)間復(fù)雜度和空間復(fù)雜度到底是什么？
5.1 最劣的情況 O(n^2)
計(jì)算最糟糕情況，就是全部逆序情況。時(shí)間復(fù)雜度為O(n^2)
比較次數(shù)和移動(dòng)次數(shù)分別為n(n-1)/2和3n(n-1)/2

我們以比較次數(shù)進(jìn)行理解
冒泡排序一共要進(jìn)行(n-1)次循環(huán),每一次循環(huán)都要進(jìn)行當(dāng)前n-1次比較。所以一共的比較次數(shù)是: 
(n-1) + (n-2) + (n-3) + … + 1 = n*(n-1)/2; 
因此冒泡排序的時(shí)間復(fù)雜度是 O(n2)。
移動(dòng)次數(shù)很好理解。會(huì)發(fā)生3次交換，因此常量系數(shù)為3。
5.1 最優(yōu)的情況 O(n)
計(jì)算優(yōu)情況時(shí)，也就是全部是順序的情況下。冒泡排序只執(zhí)行第一層for循環(huán)，而不會(huì)執(zhí)行第二層for循環(huán)。
因此冒泡排序的時(shí)間復(fù)雜度是 O(n)。
6. 冒泡排序擴(kuò)展閱讀
6.1 C語(yǔ)言版
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. 冒泡排序總結(jié)
優(yōu)點(diǎn)： 比較簡(jiǎn)單，空間復(fù)雜度較低，是穩(wěn)定的。
缺點(diǎn)： 時(shí)間復(fù)雜度太高，效率不好。
其他可看上面的小結(jié)與算法口訣。
參考文章
https://cloud.tencent.com/dev...
http://www.pianshen.com/artic...
https://blog.csdn.net/Hydra_s...
文末
歡迎關(guān)注個(gè)人微信公眾號(hào)：Coder編程
獲取最新原創(chuàng)技術(shù)文章和免費(fèi)學(xué)習(xí)資料，更有大量精品思維導(dǎo)圖、面試資料、PMP備考資料等你來領(lǐng)，方便你隨時(shí)隨地學(xué)習(xí)技術(shù)知識(shí)！
新建了一下qq群：315211365，歡迎大家進(jìn)群交流一起學(xué)習(xí)。謝謝了！也可以介紹給身邊有需要的朋友。
文章收錄至
Github: https://github.com/CoderMerli...
Gitee: https://gitee.com/573059382/c...