在排序算法的大家族中，冒泡排序是最基础也最经典的算法之一。它的核心思想简单易懂，通过重复地走访待排序序列，一次比较两个相邻的元素，若它们的顺序错误就把它们交换过来，直到没有需要交换的元素为止。虽然冒泡排序的时间复杂度较高，在大规模数据排序中并不常用，但它是理解排序算法思想的绝佳入门案例，也是计算机考研 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 考生，需重点掌握冒泡排序的时间复杂度分析、稳定性判断以及与其他算法的对比，确保在考试中能够准确解答相关问题。

希望本文能够帮助读者更深入地理解冒泡排序，并在实际项目中发挥其优势。谢谢阅读！

---

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。