冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）是一种简单但直观的排序算法，常作为学习排序算法的入门案例。本文将详细介绍冒泡排序的原理、实现方式，并通过一个例子展示排序的全过程。

一、冒泡排序的基本原理

冒泡排序的工作方式类似于水中的气泡，从底部不断向上冒。在一轮比较中，较大的元素会逐步“冒泡”到列表的末尾。

核心思想：

• 每次遍历相邻的两个元素，如果前一个比后一个大，就交换它们的位置。
• 通过多次遍历，每轮将当前未排序部分中的最大值“冒泡”到末尾。
• 随着遍历次数增加，未排序部分逐渐减少，最终整个序列变为有序。

二、冒泡排序的伪代码

步骤描述：

1. 对数组进行多轮遍历。
2. 每次从头到尾比较相邻的两个元素。
3. 如果发现逆序（即前一个元素大于后一个元素），就交换这两个元素。
4. 当一轮遍历完成后，最大元素会被放到最后。
5. 重复上述过程，直到所有元素有序。

三、冒泡排序的代码实现

public class BubbleSort {
    public static void bubbleSort(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]) { // 如果前一个大于后一个，则交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true; // 标记发生了交换
                }
            }
            if (!swapped) { // 如果没有发生交换，说明数组已排序
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2};
        System.out.println("排序前：" + java.util.Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后：" + java.util.Arrays.toString(arr));
    }
}

代码解读：

• 外层循环 i 控制需要进行的排序轮次，每轮将最大的元素放到末尾。
• 内层循环 j 负责比较相邻的元素并交换。
• 优化：引入 swapped 标志变量。如果在某轮中没有发生交换，说明数组已排序，可提前结束。

四、冒泡排序过程详解

假设我们需要对数组 [5, 3, 8, 6, 2] 进行升序排序。

五、时间复杂度与优化

时间复杂度：

1. 最坏时间复杂度：O(n^2)
   • 当数组是逆序时，需要进行最多的比较和交换。
2. 最佳时间复杂度：O(n)
   • 当数组已经有序时，内层循环不会发生交换，标志变量 swapped 能及时终止外层循环。
3. 平均时间复杂度：O(n^2)

空间复杂度：

• 冒泡排序是原地排序算法，只需常数级额外空间，空间复杂度为 O(1)。

优化：

• 通过引入标志变量 swapped，当一轮比较后没有发生交换时，提前退出算法，从而提高效率。

六、冒泡排序的优缺点

优点：

1. 实现简单，容易理解。
2. 对少量数据表现良好，适合作为入门学习算法。

缺点：

1. 时间复杂度高，不适合处理大量数据。
2. 即使数组已部分有序，仍需要完整比较（优化后可减少）。

七、总结

冒泡排序虽然效率不高，但通过学习它，我们可以掌握排序算法的基本思想和实现技巧。它的优化版本也能在部分情况下表现出较好的性能。作为入门级排序算法，冒泡排序为后续理解更复杂的排序方法（如快速排序、归并排序）打下了坚实的基础。

希望通过这篇博客，您能对冒泡排序的原理、实现和优化有全面的理解！如果对排序算法有其他疑问，欢迎留言讨论。 😊

PS：可以点击打开“冒泡排序算法演示”页面亲自体验一下 ^^