在排序算法的大家族中，冒泡排序是最基礎也最經典的算法之一。它的核心思想簡單易懂，通過重復地走訪待排序序列，一次比較兩個相鄰的元素，若它們的順序錯誤就把它們交換過來，直到沒有需要交換的元素為止。雖然冒泡排序的時間復雜度較高，在大規模數據排序中并不常用，但它是理解排序算法思想的絕佳入門案例，也是計算機考研 408 和算法學習中的基礎內容。

冒泡排序的基本概念

冒泡排序（Bubble Sort）之所以被稱為 “冒泡”，是因為在排序過程中，較小的元素會像水中的氣泡一樣逐漸 “上浮” 到序列的頂端，而較大的元素則會 “下沉” 到序列的末端。

例如，對于一個無序序列 [5, 2, 9, 1, 5, 6]，使用冒泡排序進行排序時，過程如下：

• 第一輪比較后，最大的元素 9 會 “下沉” 到序列的最后位置，序列變為 [2, 5, 1, 5, 6, 9]。

• 第二輪比較后，第二大的元素 6 會 “下沉” 到倒數第二個位置，序列變為 [2, 1, 5, 5, 6, 9]。

• 繼續重復這個過程，直到整個序列變得有序。

冒泡排序的算法思想

冒泡排序的核心思想是通過相鄰元素的比較和交換，使較大的元素逐漸 “下沉” 到序列的末端。其基本思路遵循以下步驟：

1. 遍歷序列：從序列的第一個元素開始，依次比較相鄰的兩個元素。

1. 比較與交換：如果前一個元素大于后一個元素，則交換這兩個元素的位置，確保較大的元素向后移動。

1. 重復迭代：完成一輪遍歷后，最大的元素會 “下沉” 到序列的最后一個位置。然后忽略已經 “下沉” 到位的元素，對剩余的元素重復上述遍歷、比較和交換過程。

1. 終止條件：當在一輪遍歷中沒有發生任何元素交換時，說明序列已經有序，排序結束。

冒泡排序的關鍵在于 “逐輪下沉最大元素”，每一輪排序都會確定一個元素的最終位置。對于長度為n的序列，最多需要進行n-1輪排序（在最壞情況下，即序列完全逆序時）。

冒泡排序的解題思路

使用冒泡排序解決實際問題時，通常遵循以下步驟：

1. 確定待排序序列：明確需要排序的數據集合，可以是數組、列表等數據結構。

1. 初始化控制變量：設置一個標志變量（如swapped），用于記錄在一輪遍歷中是否發生了元素交換，初始值為false。

1. 執行多輪排序：

• • 每輪遍歷從序列的第一個元素開始，到未排序部分的最后一個元素結束。

• • 在遍歷過程中，比較相鄰元素，若前大后小則交換，并將標志變量設為true。

• • 一輪遍歷結束后，檢查標志變量。若為false，說明序列已有序，退出循環；若為true，則重置標志變量，繼續下一輪排序。

1. 返回排序結果：排序完成后，返回有序的序列。

通過優化標志變量，可以避免在序列已經有序后繼續不必要的遍歷，提高算法效率。

LeetCode 例題及 Java 代碼實現

例題 1：排序數組（LeetCode 912）

給你一個整數數組 nums，請你將該數組升序排列。

解題思路

本題是典型的排序問題，可直接使用冒泡排序求解。按照上述解題思路，通過多輪遍歷、比較和交換，將數組升序排列。

Java 代碼實現

import java.util.Arrays;public class SortArray {public int[] sortArray(int[] nums) {int n = nums.length;// 外層循環控制排序輪數，最多n-1輪for (int i = 0; i < n - 1; i++) {boolean swapped = false;// 內層循環控制每輪比較的范圍，每輪結束后最大元素已沉底，無需再比較for (int j = 0; j < n - 1 - i; j++) {if (nums[j] > nums[j + 1]) {// 交換相鄰元素int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;swapped = true;}}// 若本輪無交換，說明數組已有序，提前退出if (!swapped) {break;}}return nums;}public static void main(String[] args) {SortArray solution = new SortArray();int[] nums = {5, 2, 9, 1, 5, 6};int[] sortedNums = solution.sortArray(nums);System.out.println(Arrays.toString(sortedNums)); // 輸出：[1, 2, 5, 5, 6, 9]}}

例題 2：最大間距（LeetCode 164）

給定一個無序的數組 nums，返回數組在排序之后，相鄰元素之間最大的差值。如果數組元素個數小于 2，則返回 0。

解題思路

本題可先使用冒泡排序對數組進行排序，然后遍歷排序后的數組，計算相鄰元素的差值，記錄最大差值。需要注意的是，由于冒泡排序在處理大規模數據時效率較低，本題僅作為冒泡排序應用的示例，實際解題中更推薦使用基數排序等高效算法。

Java 代碼實現

public class MaximumGap {public int maximumGap(int[] nums) {int n = nums.length;if (n < 2) {return 0;}// 先使用冒泡排序對數組排序bubbleSort(nums);// 計算相鄰元素的最大差值int maxGap = 0;for (int i = 1; i < n; i++) {maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);}return maxGap;}// 冒泡排序實現private void bubbleSort(int[] nums) {int n = nums.length;for (int i = 0; i < n - 1; i++) {boolean swapped = false;for (int j = 0; j < n - 1 - i; j++) {if (nums[j] > nums[j + 1]) {int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;swapped = true;}}if (!swapped) {break;}}}public static void main(String[] args) {MaximumGap solution = new MaximumGap();int[] nums = {3, 6, 9, 1};System.out.println(solution.maximumGap(nums)); // 輸出：3（排序后為[1,3,6,9]，最大間距為6-3=3）}}

冒泡排序與考研 408

在計算機考研 408 中，冒泡排序是數據結構部分的基礎考點，主要涉及以下幾個方面：

1. 算法原理與實現：考研 408 常考查冒泡排序的基本原理、執行過程和代碼實現。要求考生能夠手動模擬冒泡排序在給定序列上的每一步操作，包括元素的比較、交換和每輪結束后的序列狀態。例如，給定一個逆序數組，寫出冒泡排序每一輪后的結果。

1. 時間復雜度與空間復雜度分析：

• • 時間復雜度：

• • • 最壞情況：當序列完全逆序時，每輪都需要進行n-i-1次比較和交換（i為輪次），總比較次數為(n-1)+(n-2)+...+1 = n(n-1)/2，時間復雜度為\(O(n^2)\)。

• • • 最好情況：當序列已經有序時，只需進行 1 輪遍歷（n-1次比較），且無交換操作，時間復雜度為\(O(n)\)。

• • • 平均情況：時間復雜度為\(O(n^2)\)。

• • 空間復雜度：冒泡排序是原地排序算法，僅需要常數級別的額外空間（用于臨時變量和標志變量），空間復雜度為\(O(1)\)。

1. 算法特性：

• • 穩定性：冒泡排序是穩定的排序算法。在比較相鄰元素時，只有當nums[j] > nums[j+1]時才進行交換，相等元素的相對順序不會改變。

• • 原地性：不需要額外的輔助空間，直接在原序列上進行排序。

• • 適應性：通過標志變量優化后，對于接近有序的序列，效率會顯著提高（最好情況為\(O(n)\)）。

1. 與其他排序算法的對比：考研 408 中常將冒泡排序與插入排序、選擇排序等簡單排序算法進行對比，考查它們在時間復雜度、空間復雜度、穩定性、適用場景等方面的差異。例如：

• • 冒泡排序和插入排序的最好時間復雜度都是\(O(n)\)，但插入排序在實際應用中通常比冒泡排序更高效（減少了元素交換的次數）。

• • 選擇排序的時間復雜度始終為\(O(n^2)\)，且不穩定，而冒泡排序在最好情況下更優且穩定。

1. 算法優化：考研中可能會考查冒泡排序的優化方法，除了上述的標志變量優化外，還包括 “記錄最后一次交換的位置”，以此確定下一輪遍歷的終點（因為最后一次交換位置之后的元素已經有序），進一步減少比較次數。

總結

冒泡排序作為最基礎的排序算法之一，雖然在大規模數據排序中效率不高，但其簡單直觀的思想和清晰的執行過程，使其成為理解排序算法的入門首選。通過本文的學習，我們掌握了冒泡排序的算法思想、解題思路、LeetCode 實戰應用以及考研 408 中的考點。

在學習過程中，建議結合手動模擬排序過程加深對算法的理解，同時對比其他簡單排序算法（如插入排序、選擇排序）的異同，形成系統的知識體系。對于考研 408 考生，需重點掌握冒泡排序的時間復雜度分析、穩定性判斷以及與其他算法的對比，確保在考試中能夠準確解答相關問題。

希望本文能夠幫助讀者更深入地理解冒泡排序，并在實際項目中發揮其優勢。謝謝閱讀！

---

希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方，請隨時告訴我。