1. 概述
本文将介绍冒泡排序（Bubble Sort）算法，包括其基本实现和优化版本，并对它们的时间复杂度进行详细分析。
2. 算法原理
冒泡排序是一种基础排序算法，其核心思想是通过不断交换相邻逆序元素，将较大的元素“冒泡”到数组末尾。整个过程类似于水泡在水中逐渐上浮，因此得名“冒泡排序”。
2.1 标准冒泡排序伪代码
algorithm bubbleSort(A):
// INPUT
// A = input array
// OUTPUT
// Sorted A
N <- length(A)
for j <- 1 to N:
for i <- 0 to N - 1:
if A[i] > A[i + 1]:
temp <- A[i]
A[i] <- A[i + 1]
A[i + 1] <- temp
2.2 算法步骤说明
- 初始时，从数组第一个元素开始，依次比较相邻两个元素。
- 若前一个元素大于后一个元素，则交换两者位置。
- 每轮遍历结束后，当前未排序部分的最大元素会“冒泡”到数组末尾。
- 重复上述过程，直到所有元素排序完成。
2.3 优化版本（加入交换标志）
为提升性能，可以引入一个交换标志 indicator，用于检测当前轮次是否发生交换。如果某轮没有发生交换，说明数组已经有序，可提前终止排序。
algorithm improvedBubbleSort(A):
// INPUT
// A = input array
// OUTPUT
// Sorted A
N <- length(A)
indicator <- 1
j <- 0
while indicator == 1 and j < N:
j <- j + 1
indicator <- 0
for i <- 1 to N - 1:
if A[i] > A[i + 1]:
temp <- A[i]
A[i] <- A[i + 1]
A[i + 1] <- temp
indicator <- 1
✅ 优点：
- 在数组已经有序的情况下，可提前退出，减少不必要的比较和交换。
❌ 缺点：
- 优化版本在最坏和平均情况下的时间复杂度仍为 O(N²)，仅在最佳情况下有所提升。
3. 时间复杂度分析
3.1 标准冒泡排序
最坏情况（逆序）：
每轮都需要进行交换，总比较次数为：
$$ (N - 1) + (N - 2) + \cdots + 1 = \frac{N(N - 1)}{2} = \mathcal{O}(N^2) $$平均情况：
依然需要进行大量比较和交换，时间复杂度为： $$ \mathcal{O}(N^2) $$最好情况（已排序）：
仍需进行完整遍历，时间复杂度仍为： $$ \mathcal{O}(N^2) $$
3.2 优化冒泡排序
最坏情况 & 平均情况：
与标准版本一致，时间复杂度为： $$ \mathcal{O}(N^2) $$最好情况（已排序）：
仅需一次遍历即可确认有序，时间复杂度为： $$ \mathcal{O}(N) $$
⚠️ 注意：虽然优化版本在某些情况下效率更高，但在大规模数据中仍不推荐使用。
4. Java 实现示例
以下是标准冒泡排序的 Java 实现：
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int j = 0; j < n - 1; j++) {
for (int i = 0; i < n - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
// Swap arr[i] and arr[i + 1]
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
}
优化版本实现如下：
public class ImprovedBubbleSort {
public static void improvedBubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果本轮没有发生交换，说明数组已有序
if (!swapped) break;
}
}
}
5. 优缺点分析
✅ 优点
- 实现简单，逻辑清晰，适合教学入门。
- 是稳定排序算法（Stable Sort），适用于需要保持相同元素相对顺序的场景。
- 对几乎有序的数据效率较高。
❌ 缺点
- 时间复杂度高，尤其在数据量大时效率极低。
- 与插入排序相比，虽然渐近复杂度相同，但冒泡排序的交换次数更多，性能更差。
- 在现代 CPU 上，由于缓存利用率低，实际运行效率较差。
6. 总结
冒泡排序是一种基础但效率较低的排序算法。虽然其时间复杂度在最坏和平均情况下为 O(N²)，但在数据量小或数据基本有序时仍有一定的使用价值。通过引入交换标志，可以优化其在最佳情况下的性能，使其提前终止，从而减少不必要的比较和交换操作。
📌 建议：
- 适合教学或小数据集排序。
- 实际项目中应优先考虑更高效的排序算法，如快速排序、归并排序或 Java 中的
Arrays.sort()。
如需了解冒泡排序在 Java 中的具体应用，请参考我们的 Java 冒泡排序实现教程。