1.3 冒泡排序

ITCharge大约 4 分钟

1.3 冒泡排序

---

1. 冒泡排序算法思想

冒泡排序（Bubble Sort）基本思想：
通过相邻元素的比较与交换，将较大的元素逐步「冒泡」到数组末尾，较小的元素自然「下沉」到数组开头。

冒泡排序的名字来源于这个过程：就像水中的气泡从底部向上浮到水面一样，较大的元素会逐步移动到数组的末尾。

我们使用「冒泡」的方式来模拟一下这个过程：

将数组元素想象成大小不同的「泡泡」，值越大的元素「泡泡」越大。
从左到右依次比较相邻的两个元素。
如果左侧元素大于右侧元素，则交换位置。
每完成一趟遍历，最大的元素就会「浮」到最右侧。

<1>

<2>

<3>

<4>

<5>

<6>

<7>

2. 冒泡排序算法步骤

对于长度为 $n$ 的数组，冒泡排序的步骤如下：

第 $1$ $1$ 趟冒泡：对前 $n$ $n$ 个元素依次比较相邻元素，将较大的元素向右交换，最终使最大值移动到数组末尾（第 $n$ $n$ 个位置）。
1. 比较第 $1$ 个和第 $2$ 个元素，若前者大于后者则交换。
2. 比较第 $2$ 个和第 $3$ 个元素，若前者大于后者则交换。
3. 以此类推，直到比较第 $n - 1$ 个和第 $n$ 个元素。
4. 完成后，最大元素已位于末尾。
第 $2$ $2$ 趟冒泡：对前 $n-1$ $n - 1$ 个元素重复上述过程，将次大值移动到倒数第二个位置（第 $n-1$ $n - 1$ 个位置）。
1. 比较第 $1$ 个和第 $2$ 个元素，若前者大于后者则交换。
2. 比较第 $2$ 个和第 $3$ 个元素，若前者大于后者则交换。
3. 以此类推，直到比较第 $n-2$ 个和第 $n-1$ 个元素。
4. 完成后，次大元素已位于倒数第二位。
持续进行上述冒泡过程，每一趟比较的元素个数递减，直到某一趟未发生任何交换，说明数组已完全有序，排序结束。

以数组 $[5, 2, 3, 6, 1, 4]$ 为例，演示一下冒泡排序的算法步骤。

3. 冒泡排序代码实现

class Solution:
    def bubbleSort(self, nums: [int]) -> [int]:
        """冒泡排序算法实现"""
        n = len(nums)
        # 外层循环控制趟数，每一趟将当前未排序区间的最大值“冒泡”到末尾
        for i in range(n - 1):
            swapped = False  # 记录本趟是否发生过交换
            # 内层循环负责相邻元素两两比较，将较大值后移
            for j in range(n - i - 1):
                # 如果前一个元素大于后一个元素，则交换
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
                    swapped = True  # 发生了交换
            # 如果本趟没有发生任何交换，说明数组已经有序，可以提前结束
            if not swapped:
                break
        return nums  # 返回排序后的数组

    def sortArray(self, nums: [int]) -> [int]:
        """排序数组的接口，调用冒泡排序"""
        return self.bubbleSort(nums)

4. 冒泡排序算法分析

指标	复杂度	说明
最佳时间复杂度	$O(n)$	数组已有序，只需一趟遍历
最坏时间复杂度	$O(n^2)$	数组逆序，需要 $n$ 趟遍历
平均时间复杂度	$O(n^2)$	一般情况下的复杂度
空间复杂度	$O(1)$	原地排序，只使用常数空间
稳定性	✅ 稳定	相等元素相对位置不变

适用场景：

数据量较小（ $n < 50$ ）
数据基本有序

5. 总结

冒泡排序是最简单的排序算法之一，通过相邻元素比较交换实现排序。虽然实现简单，但效率较低。

优点：实现简单，稳定排序，空间复杂度低
缺点：时间复杂度高，交换次数多

练习题目

0912. 排序数组（冒泡排序会超时，仅作练习）
0283. 移动零（冒泡排序会超时，仅作练习）
排序算法题目列表

参考资料

【文章】11.3. 冒泡排序 - Hello 算法