算法解析

冒泡排序是最基础的排序算法，由于其直观性，经常作为首个介绍的排序算法。其原理为：

• 内循环： 使用相邻双指针 j , j + 1 从左至右遍历，依次比较相邻元素大小，若左元素大于右元素则将它们交换；遍历完成时，最大元素会被交换至数组最右边 。

• 外循环： 不断重复「内循环」，每轮将当前最大元素交换至 剩余未排序数组最右边 ，直至所有元素都被交换至正确位置时结束。

如下图所示，首轮「内循环」后，数组最大元素已被交换至数组最右边；接下来，只需要完成数组剩余 $N-1$ 个元素的排序即可（设数组元素数量为 $N$ ）。同理，对剩余 $N-1$ 个元素执行「内循环」，可将第二大元素交换至剩余数组最右端，以此类推……

1 / 10

如下图所示，冒泡排序的「外循环」共 $N-1$ 轮，每轮「内循环」都将当前最大元素交换至数组最右边，从而完成对整个数组的排序。

如下图所示，为示例数组 nums = [4, 1, 3, 1, 5, 2] 的冒泡排序算法运行过程。

1 / 29

代码

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):           # 外循环
        for j in range(N - i - 1):   # 内循环
            if nums[j] > nums[j + 1]:
                # 交换 nums[j], nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

算法特性

• 时间复杂度 $O(N^2)$ ：

  • 最佳 $\Omega (N)$ ： 普通冒泡排序的时间复杂度恒为 $O(N^2)$ ，对于近似排序数组，通过加入标志位可实现提前返回（详情请见下文）。
  • 平均与最差 $O(N^2)$ ：「外循环」共 $N-1$ 轮，使用 $O(N)$ 时间；每轮「内循环」分别遍历 $N-1$ , $N-2$ , $\cdots$ , $2$ , $1$ 次，平均 $\frac{N}{2}$ 次，使用 $O(\frac{N}{2})=O(N)$ 时间；因此，总体时间复杂度为 $O(N^2)$ 。

• 空间复杂度 $O(1)$ ： 只需原地交换元素，使用常数大小的额外空间。

• 冒泡排序是通过不断 交换元素 实现排序（交换 2 个元素需要 3 次赋值操作），因此速度较慢；

• 原地： 指针变量仅使用常数大小额外空间，空间复杂度为 $O(1)$ ；

• 稳定： 元素值相同时不交换，因此不会改变相同元素的相对位置；

• 自适应： 通过增加一个标志位 flag ，若某轮内循环未执行任何交换操作时，说明已经完成排序，因此直接返回。此优化使冒泡排序的最优时间复杂度达到 $O(N)$（当输入数组已排序时）；

算法优化

普通冒泡排序的时间复杂度恒为 $O(N^2)$​ ，与输入数组的元素分布无关。

通过增加一个标志位 flag ，若在某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序，直接返回结果即可。

优化后的冒泡排序的最差和平均时间复杂度仍为 $O(N^2)$ ；在输入数组 已排序 时，达到 最佳时间复杂度 $\Omega (N)$ 。

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):
        flag = False         #  初始化标志位
        for j in range(N - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 记录交换元素
        if not flag: break   # 内循环未交换任何元素，则跳出