零、📃前言

??想要養成 「演算法思維」，每一個簡單的問題都要思考它背后的真正含義，做到 舉一反三，觸類旁通，
??「 冒泡排序 」 是最好理解且編碼最簡單的排序演算法，所以一般各種 「資料結構」 的教科書上都會一并進行講解，于是，我也來講一講，我會盡量做到「深入淺出」，讓 90% 的 「零基礎小白 」 也都能理解，真正做到 「讓天下沒有難學的演算法」 ，我知道這很難，但是我愿意嘗試！我用我最好的青春，寫下了這篇文章，

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌

那么，我的教程和別人的教程有什么不同的地方呢？
??「第一步」簡單釋義： 我會解釋一下這個演算法的目的、思想、以及為什么叫這個名字以幫助記憶，
??「第二步」核心思想： 大致介紹一下這個演算法的核心思想，
??「第三步」動圖演示： 引入一個動圖，并且用一個切實的例子展示一下演算法執行的全程序，
??「第四步」演算法前置： 在學習這個演算法之前，我們需要學習的前置內容有哪些？這些內容是需要事先去攻克的，
??「第五步」演算法描述： 細致的講解整個演算法的執行流程，
??「第六步」演算法分析： 對演算法的時間復雜度和空間復雜度進行一個詳細的分析，
??「第七步」優化方案： 介紹一些可以優化的點，
??「第八步」代碼實踐： 用 C/C++ 來實作上述演算法，
??「第九步」代碼驗證： 推薦一些比較好用的在線評測系統來驗證我們實作的演算法的正確性，

一、🎯簡單釋義

1、演算法目的

??將原本亂序的陣列變成有序，可以是 「升序」 或者 「降序」 （為了描述統一，本文一律只討論 「 升序」 的情況），

2、演算法思想

??通過不斷比較相鄰的元素，如果「左邊的元素」 大于 「右邊的元素」，則進行「交換」，直到所有相鄰元素都保持升序，則演算法結束，

3、命名由來

??數值大的元素經過交換，不斷到達陣列的尾部，就像氣泡，逐漸浮出水面一樣，故此命名 「 冒泡排序 」 ，

二、🧡核心思想

• 「迭代」：類似的事情，不停地做，
• 「比較」：關系運算子 大于( > \gt >) 的運用，
• 「交換」：變數或者物件的值的互換，

三、🔆動圖演示

1、樣例

• 初始情況下的資料如 圖二-1-1 所示，基本屬于亂序，純隨機出來的資料，

2、演算法演示

• 接下來，我們來看下排序程序的影片演示，如 圖二-2-1 所示：

3、樣例說明

??我們看到，首先需要將 「第一個元素」 和 「第二個元素」 進行 「比較」，如果 前者 大于 后者，則進行 「交換」，然后再比較 「第二個元素」 和 「第三個元素」 ，以此類推，直到 「最大的那個元素」 被移動到 「最后的位置」 ，
??然后，進行第二輪「比較」，直到 「次大的那個元素」 被移動到 「倒數第二的位置」 ，
??最后，經過一定輪次的「比較」 和 「交換」之后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

• 這個演算法本身需要做一些「 回圈 」進行迭代計算，所以你至少需要知道「 回圈 」 的含義，這里以 「 c++ 」 為例，來看下一個簡單的「 回圈 」是怎么寫的，代碼如下：

int n = 520;
for(int i = 0; i < n; ++i) {
    // 回圈體
}

• 這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 520 520 520，也就是會執行 520 520 520 次，
• 具體的語法細節不是本文的主要內容，請自行學習，

2、比較的實作

• 「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「大于運算子（即 >）」 ，
• 我們可以將兩個數的「比較」寫成一個函式isBigger，以 「 c++ 」 為例，實作如下：

#define Type int
bool isBigger(Type a, Type b) {
    return a > b;
}

• 其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、交換的實作

• 所謂「交換」，就是對于兩個變數，將它們的值進行互換，
• 在 「Python」 中，我們可以直接寫出下面這樣的代碼就實作了變數的交換，

a, b = b, a

• 在 「 c++ 」 里，這個語法是錯誤的，
• 我們可以這么理解，你有兩個杯子 a a a 和 b b b，兩個杯子里都盛滿了水，現在想把兩個杯子里的水「交換」一下，那么第一個想到的方法是什么？

當然是再找來一個臨時杯子：
??1）先把 a a a 杯子的水倒進這個臨時的杯子里；
??2）再把 b b b 杯子的水倒進 a a a 杯子里；
??3）最后把臨時杯子里的水倒進 b b b 杯子；

• 這種就是臨時變數法，以 「 c++ 」 為例，實作如下：

#define Type int
void swap(Type* a, Type* b) {
    Type tmp = *a;     // 把 a 杯子的水倒進臨時杯子
    *a = *b;           // 把 b 杯子的水倒進 a 杯子
    *b = tmp;          // 把 臨時杯子 的水 倒進 b 杯子
}

• 這里*涉及到的「指標」相關知識，屬于語法層面，請自行學習，

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「 冒泡排序 」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1） 回圈迭代變數 i = 0 → n ? 1 i = 0 \to n-1 i=0→n?1；
??2） 每次迭代，令 j = i j = i j=i，回圈執行比較 a [ j ] a[j] a[j] 和 a [ j + 1 ] a[j+1] a[j+1]，如果產生 a [ j ] > a [ j + 1 ] a[j] \gt a[j+1] a[j]>a[j+1] 則交換兩者的值，然后執行 j = j + 1 j = j + 1 j=j+1，這時候對 j j j 進行判斷，如果 j ≥ n ? 1 j \ge n-1 j≥n?1，則回到 1），否則繼續執行 2），

六、🧶演算法分析

1、時間復雜度

• 我們假設 「比較」 和 「交換」 的時間復雜度為 O ( 1 ) O(1) O(1)（為什么這里說假設，因為有可能要「比較」的兩個元素本身是陣列，并且是不定長的，所以只有當系統內置型別，我們才能說這兩個操作是 O ( 1 ) O(1) O(1) 的），
• 「 冒泡排序 」 中有兩個嵌套回圈，

外回圈正好運行 n ? 1 n-1 n?1 次迭代， 但內部回圈運行變得越來越短：
??當 i = 0 i = 0 i=0，內層回圈 n ? 1 n-1 n?1 次「比較」操作，
??當 i = 1 i = 1 i=1，內層回圈 n ? 2 n-2 n?2 次「比較」操作，
??當 i = 2 i = 2 i=2，內層回圈 n ? 3 n-3 n?3 次「比較」操作，
??……
??當 i = n ? 2 i = n-2 i=n?2，內層回圈 1 1 1 次「比較」操作，
??當 i = n ? 1 i = n-1 i=n?1，內層回圈 0 0 0 次「比較」操作，

• 因此，總「比較」次數如下：
• ( n ? 1 ) + ( n ? 2 ) + . . . + 1 + 0 = n ( n ? 1 ) 2 (n-1) + (n-2) + ... + 1 + 0 = \frac {n(n-1)}{2} (n?1)+(n?2)+...+1+0=2n(n?1)?
• 總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)

2、空間復雜度

• 由于演算法在執行程序中，只有「交換」變數時候采用了臨時變數的方式，而其它沒有采用任何的額外空間，所以空間復雜度為 O ( 1 ) O(1) O(1)，

七、🧢優化方案

??「 冒泡排序 」在眾多排序演算法中效率較低，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，
?? 想象一下，當有 n = 1 0 5 n = 10^5 n=105 個數字， 即使我們的計算機速度超快，并且可以在 1 秒內計算 1 0 8 10^8 108 次操作，但冒泡排序仍需要大約一百秒才能完成，
??但是，它的外層回圈是可以提前終止的，例如，假設一開始所有數字都是升序的，那么在首輪「比較」的時候沒有發生任何的「交換」，那么后面也就不需要繼續進行 「比較」 了，直接跳出外層回圈，演算法提前終止，

• 「改進思路」如果我們通過內部回圈完全不交換，這意味著陣列已經排好序，我們可以在這個點上停止演算法，

八、💙代碼實踐

#include <stdio.h>

int a[1010];

void input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void BubbleSort(int n, int *a) {             // (1)
    bool swapped;
    int last = n;
    do {
        swapped = false;                     // (2)
        for(int i = 0; i < last - 1; ++i) {  // (3)
            if(a[i] > a[i+1]) {              // (4)
                swap(&a[i], &a[i+1]);        // (5)
                swapped = true;              // (6)
            }
        }
        --last;
    }while (swapped);
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        input(n, a);
        BubbleSort(n, a);
        output(n, a);
    }
    return 0;
} 

• ( 1 ) (1) (1) void BubbleSort(int n, int *a)為冒泡排序的實作，代表對a[]陣列進行升序排序，
• ( 2 ) (2) (2) swapped標記本輪迭代下來，是否有元素產生了交換，
• ( 3 ) (3) (3) 每次冒泡的結果，會執行last的自減，所以待排序的元素會越來越少，
• ( 4 ) (4) (4) 如果發現兩個相鄰元素產生逆序，則將它們進行交換，保證右邊的元素一定不比左邊的小，
• ( 5 ) (5) (5) swap實作了元素的交換，這里需要用&轉換成地址作為傳參，
• ( 6 ) (6) (6) 標記更新，一旦標記更新，則代表進行了交換，所以下次迭代必須繼續，

九、💗代碼驗證

• 我寫文章并不是為了推廣什么網站，所以我只會告訴大家方法，具體驗證方式還請自行抉擇，
• 比如，你可以在百度上搜索 代碼在線提交、OnlineJudge、HDOJ、LeetCode、洛谷、POJ 等等的關鍵詞，然后去找對應的題目提交驗證你的代碼的正確性，

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌