---

📑冒泡排序介紹

冒泡排序是一種簡單但效率較低的排序算法。它重復地比較相鄰的兩個元素，如果順序不對則交換它們，直到所有元素都被比較過一次。這樣每一輪比較過后，最大的元素就會"冒泡"到最后面。接著，算法將會忽略最后一個元素，重復上述比較和交換的過程，直到所有元素都按照順序排列。

? 冒泡排序算法的步驟如下：

1. 從數組的第一個元素開始，依次比較相鄰的兩個元素。
2. 如果前一個元素大于后一個元素，交換它們的位置。
3. 繼續比較下一對相鄰元素，直到最后一個元素。
4. 重復以上步驟，每一輪比較都會將最大的元素"冒泡"到最后面。
5. 當比較結束時，此時數組已經排好序，排序結束。

動圖演示如下：

🌤?代碼實現

🌳C語言版

// 交換函數，用于交換數組中兩個元素的位置
void swap(int* arr, int i, int j) {int tmp = arr[i];  // 將第一個元素的值存儲在臨時變量 tmp 中arr[i] = arr[j];   // 將第二個元素的值賦給第一個元素的位置arr[j] = tmp;      // 將臨時變量 tmp 的值賦給第二個元素的位置
}// 冒泡排序函數，用于對數組進行排序
void bobbleSort(int* arr, int n) {// 外層循環控制需要遍歷的輪數，共進行 n-1 次遍歷for (int i = 0; i < n - 1; i++) {// 內層循環進行相鄰元素的比較和交換// j 的范圍是從 0 到 n-i-1，這樣每次內層循環可以比較并將最大值移動到最后for (int j = 0; j < n - i - 1; j++) { // j 進循環的條件容易出錯，特殊標記下// 如果前一個元素比后一個元素大，交換它們if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);  // 調用交換函數進行交換}}}
}

🌳java版

// 交換函數，用于交換數組中兩個元素的位置
private static void swap(int[] array, int i, int j) {int tmp = array[i]; // 將第一個元素的值存儲在臨時變量 tmp 中array[i] = array[j]; // 將第二個元素的值賦給第一個元素的位置array[j] = tmp; // 將臨時變量 tmp 的值賦給第二個元素的位置
}// 冒泡排序函數，用于對數組進行排序
public static void bubbleSort(int[] array) {// 外層循環控制需要遍歷的輪數for (int i = 0; i < array.length; i++) {// 內層循環進行相鄰元素的比較和交換for (int j = i + 1; j < array.length; j++) {// 如果前一個元素比后一個元素大，交換它們if (array[i] > array[j]) {swap(array, i, j); // 調用交換函數進行交換}}}
}

🌤?做個簡單的優化

可以在內層循環中定義一個變量 flag：用于檢測這一輪內層循環是否發生了交換。初始值設為 1。
如果在一輪內層循環中沒有發生交換（flag 仍為 1），說明數組已經有序，跳出循環即可。
🌳C語言版

// 交換函數，用于交換數組中兩個元素的位置
void swap(int* arr, int i, int j) {int tmp = arr[i];  // 將第一個元素的值存儲在臨時變量 tmp 中arr[i] = arr[j];   // 將第二個元素的值賦給第一個元素的位置arr[j] = tmp;      // 將臨時變量 tmp 的值賦給第二個元素的位置
}// 冒泡排序函數，用于對數組進行排序
void bobbleSort(int* arr, int n) {// 外層循環控制需要遍歷的輪數，共進行 n-1 次遍歷for (int i = 0; i < n - 1; i++) {int flag = 1; // 標記用于檢測這一輪是否發生了交換// 內層循環進行相鄰元素的比較和交換// j 的范圍是從 0 到 n-i-1，這樣每次內層循環可以比較并將最大值移動到最后for (int j = 0; j < n - i - 1; j++) { // j 進循環的條件容易出錯，特殊標記下// 如果前一個元素比后一個元素大，交換它們if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1); // 調用交換函數進行交換flag = 0; // 發生交換后，將標記設置為 0}}// 如果沒有發生交換，說明數組已經有序，提前退出排序if (flag) {break;}}
}

🌳java版

// 交換函數，用于交換數組中兩個元素的位置
private static void swap(int[] array, int i, int j) {int tmp = array[i];  // 將第一個元素的值存儲在臨時變量 tmp 中array[i] = array[j]; // 將第二個元素的值賦給第一個元素的位置array[j] = tmp;      // 將臨時變量 tmp 的值賦給第二個元素的位置
}public static void bubbleSort(int[] array) {// 外層循環控制需要遍歷的輪數，共進行 array.length 次遍歷for (int i = 0; i < array.length; i++) {boolean flg = true; // 標記用于檢測這一輪是否發生了交換// 內層循環進行相鄰元素的比較和交換// j 的范圍是從 i+1 到 array.length，注意這里的起始點是 i+1for (int j = i + 1; j < array.length; j++) {// 如果前一個元素比后一個元素大，交換它們if (array[i] > array[j]) {swap(array, i, j); // 調用交換函數進行交換flg = false; // 發生交換后，將標記設置為 false}}// 如果沒有發生交換，說明數組已經有序，提前退出排序if (flg) {break;}}
}

🌤?復雜度和穩定性分析

時間復雜度分析：在最壞的情況下，冒泡排序需要進行n-1輪比較，每輪比較需要進行n-i次。因此，總的比較次數為(n-1) + (n-2) + … + 2 + 1 = n(n-1)/2，近似為O(n²)。

空間復雜度分析：使用了常數個變量，因此空間復雜度為O(1)

什么是穩定性？
答：穩定性指的是相同的數據所在的位置經過排序后是否發生變化。換句話說就是大小相同的兩個值在排序之前和排序之后的先后順序不變，這就是穩定的。

穩定性分析：冒泡排序將小的元素往前調或者把大的元素往后調；比較的是相鄰的兩個元素，交換也發生在這兩個元素之間；因為相等的元素不會進行交換,所以穩定。

總結： 冒泡排序的時間復雜度為O(N²)，空間復雜度為O(1)，而且是穩定的排序。

---

??結語

請給自己些耐心，不要急于求成。
山外青山樓外樓，莫把百尺當盡頭。
保持空杯心態加油努力吧！

---

都看到這里啦！真棒(*^▽^*)

可以給作者一個免費的贊贊嗎，這將會鼓勵我繼續創作，謝謝大家

如有紕漏或錯誤，歡迎指正

---