冒泡排序是一种简单的排序算法，通过相邻元素的比较和交换，使较大的元素逐渐"浮"到数组末尾。

时间复杂度:最佳 O(n) | 平均 O(n²) | 最差 O(n²)

空间复杂度:O(1)

稳定性:稳定

应用场景/前提条件

适用于小规模数据
对几乎已排序的数据效率较高

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换它们
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
这步做完后，最后的元素会是最大的数
针对所有的元素重复以上的步骤，除了已经是最大数的最后一个
持续每次对越来越少(每次重复都会少一个最大数)的元素重复上面的步骤，直到没有任何一对数字需要比较

public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {// 每次遍历后，最大的i+1个元素已经排好序for (int j = 0; j < n - i - 1; j++) {// 如果当前元素大于下一个元素，则交换if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}

外层循环：控制排序的轮数。对于长度为 n 的数组，需要进行 n-1 轮排序。每一轮排序都会将当前未排序部分的最大元素 "冒泡" 到右侧。

内层循环：负责比较相邻元素并在必要时交换它们。每一轮排序后，最大的元素已经就位，因此内层循环的次数可以逐轮减少（通过n - i - 1实现）。

1. 每轮排序后的有序元素
冒泡排序的特点是：每一轮结束后，最大的 i+1 个元素都会被排到数组的右侧（升序排序）。例如：第 1 轮后，最大的元素被排到了最后一个位置。
第 2 轮后，第二大的元素被排到了倒数第二个位置。
依此类推，第 i 轮后，最大的 i+1 个元素都已经在正确的位置上。2. 内层循环的边界
由于右侧的 i+1 个元素已经有序，下一轮比较时就不需要再考虑它们。因此，
每一轮需要比较的元素数量是逐渐减少的：第 1 轮需要比较 n-1 次（所有元素都参与比较）。
第 2 轮需要比较 n-2 次（最后一个元素已经有序，不需要再比较）。
第 i 轮需要比较 n - i - 1 次。3. 为什么是 n - i - 1？n 是数组的总长度。
i 是当前外层循环的轮数（从 0 开始计数）。
n - i 表示剩余未排序元素的数量。
由于每次比较的是相邻的两个元素，因此需要进行 n - i - 1 次比较。

元素交换：当发现相邻元素顺序错误时（前一个元素大于后一个元素），通过临时变量temp交换它们的位置。

 if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}

优缺点

优点

代码简单，容易实现
适合小规模数据排序
对于几乎已经排好序的数据，效率较高
稳定的排序算法

缺点

时间复杂度高，为O(n²)
随着元素数量增加，效率急剧下降
每次只能将一个元素移动到其最终位置，效率不高

鸡尾酒排序（双向冒泡排序）

鸡尾酒排序是冒泡排序的一种变体，它从低到高然后从高到低来回排序，比冒泡排序的效率稍微高一点：

public static void cocktailSort(int[] arr) {boolean swapped = true;int start = 0;                  // 左侧已排序边界int end = arr.length - 1;       // 右侧已排序边界while (swapped) {// 从左到右扫描，将最大元素移到右侧swapped = false;for (int i = start; i < end; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);swapped = true;}}// 扫描结束后，最大元素已在end位置，因此下次扫描到end-1即可end--;// 如果没有交换，说明数组已排序if (!swapped) break;// 从右到左扫描，将最小元素移到左侧swapped = false;for (int i = end - 1; i >= start; i--) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);swapped = true;}}// 扫描结束后，最小元素已在start位置，因此下次从start+1开始start++;}
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

测验

冒泡排序的平均时间复杂度是多少？
冒泡排序是稳定的排序算法吗？
对于已经排好序的数组，优化版冒泡排序的时间复杂度是多少？
冒泡排序每一轮遍历后，数组尾部会有什么特点？
如何优化冒泡排序以提高效率？

测验答案

冒泡排序的平均时间复杂度是O(n²)。
是的，冒泡排序是稳定的排序算法。因为只有当前一个元素大于后一个元素时才交换，相等元素不会改变相对位置。
对于已经排好序的数组，优化版冒泡排序的时间复杂度是O(n)。因为第一轮遍历不会发生交换，优化版会检测到这点并提前终止。
冒泡排序每一轮遍历后，数组尾部会有一个元素到达其最终位置，且是当前未排序部分中的最大元素。第i轮结束后，末尾i个元素已排好序。
优化冒泡排序的方法:
添加标志位跟踪是否发生交换，无交换则提前终止
记录最后一次交换位置，下一轮只遍历到该位置
使用双向冒泡(鸡尾酒排序)，同时将最大值上浮和最小值下沉