冒泡排序：简单又易于实现的排序算法

大家好，今天我们来聊聊 冒泡排序（Bubble Sort）算法。听名字是不是很简单，感觉就像是水面上泡泡一样？没错，冒泡排序的名字来源于这种排序过程中，较大的元素像气泡一样逐步“冒泡”到数组的顶端。虽然它不是效率最高的排序算法，但它的简单性和易理解性使得它成为计算机科学入门算法之一。

在这篇博客中，我们将一步步了解冒泡排序的工作原理，分析它的时间复杂度，并通过 Java 代码实现这一经典算法。

一、什么是冒泡排序？

冒泡排序是一种交换排序算法，它通过多次遍历待排序的元素列表，每次比较相邻的两个元素，如果它们的顺序错误，就交换它们的位置。这样，每一轮比较都会将当前未排序部分的最大元素“冒泡”到正确的位置。

冒泡排序的步骤：

1. 从数组的第一个元素开始，比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换它们。
3. 每一轮遍历都会将当前未排序部分的最大元素移到数组的末尾。
4. 重复步骤 1 和步骤 2，直到所有元素都排好序。

二、冒泡排序的工作原理

假设我们有一个数组 [5, 3, 8, 4, 2]，我们来演示一下冒泡排序的过程：

1. 第一轮遍历：

   • 比较 5 和 3，5 > 3，交换它们，得到 [3, 5, 8, 4, 2]
   • 比较 5 和 8，5 < 8，不交换
   • 比较 8 和 4，8 > 4，交换它们，得到 [3, 5, 4, 8, 2]
   • 比较 8 和 2，8 > 2，交换它们，得到 [3, 5, 4, 2, 8]
   • 第一轮结束，最大的元素 8 被冒泡到数组的最后。

2. 第二轮遍历：

   • 比较 3 和 5，3 < 5，不交换
   • 比较 5 和 4，5 > 4，交换它们，得到 [3, 4, 5, 2, 8]
   • 比较 5 和 2，5 > 2，交换它们，得到 [3, 4, 2, 5, 8]
   • 第二轮结束，第二大的元素 5 被冒泡到倒数第二的位置。

3. 第三轮遍历：

   • 比较 3 和 4，3 < 4，不交换
   • 比较 4 和 2，4 > 2，交换它们，得到 [3, 2, 4, 5, 8]
   • 第三轮结束，第三大的元素 4 被冒泡到倒数第三的位置。

4. 第四轮遍历：

   • 比较 3 和 2，3 > 2，交换它们，得到 [2, 3, 4, 5, 8]
   • 第四轮结束，剩下的元素已经排好序。

到此为止，整个数组已经排好序了，排序结果是 [2, 3, 4, 5, 8]。

三、冒泡排序的时间复杂度

冒泡排序的时间复杂度是 O(n²)，其中 n 是数组的元素数量。原因如下：

• 在最坏的情况下，冒泡排序需要进行 n-1 次遍历，每次遍历最多进行 n-1 次比较和交换操作。
• 所以，时间复杂度是 O(n²)，这也是为什么冒泡排序对于大规模数据集来说效率较低。

最好情况：

• 如果数组已经是有序的，冒泡排序只需要进行一次遍历，时间复杂度为 O(n)。

最坏情况：

• 如果数组是倒序的，冒泡排序需要进行完全的遍历，时间复杂度为 O(n²)。

四、冒泡排序的空间复杂度

冒泡排序是原地排序算法，也就是说它只需要常数级的额外空间来交换元素。因此，它的空间复杂度为 O(1)。

下面是一个用 Java 实现的冒泡排序代码：

public static void sort(int[] arr) {
        int len = arr.length;
        for (int j = 0; j < len; j++) {
            for (int i = 0; i < len - j - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i + 1];
                    arr[i + 1] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    }

我们输入数组 {64, 34, 25, 12, 22, 11, 90}，程序的输出是：

原始数组：
64 34 25 12 22 11 90 
排序后的数组：
11 12 22 25 34 64 90