在计算机科学中，排序算法是将一组数据按照特定顺序（通常是升序或降序）重新排列的过程。我们生活中经常需要排序，比如手机相册按日期排序照片，购物清单按字母排序商品，这些背后都是排序算法在发挥作用。而冒泡排序（Bubble Sort）是最简单的排序算法之一，它的核心思想就像水中的气泡一样——大的元素会“冒”到数组的末尾。
一、冒泡排序的基本思想¶
想象一下，你有一堆大小不一的石子，需要把它们按从小到大排列。冒泡排序的思路是：从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个比后一个大，就交换它们的位置。经过一轮比较后，最大的元素会“冒泡”到数组的最后一位；接着对剩下的元素重复这个过程，直到所有元素都排好序。
举个例子：要排序数组 [5, 3, 8, 4, 2]。
- 第一轮：比较相邻元素，把最大的数“推”到末尾。
- 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，已排好。 -
第二轮：对前4个元素
[3, 5, 4, 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, 2]重复比较，把第三大的数推到倒数第三位。 - 3 和 4 比较：3 < 4，不交换
- 4 和 2 比较：4 > 2，交换 →
[3, 2, 4, 5, 8] -
此时数组倒数第三位是第三大的数
4，已排好。 -
第四轮：对前2个元素
[3, 2]比较，把第四大的数推到倒数第四位。 - 3 和 2 比较：3 > 2，交换 →
[2, 3, 4, 5, 8] - 此时数组已完全有序，排序结束。
二、冒泡排序的步骤详解¶
冒泡排序的核心步骤可以总结为以下几点：
- 确定数组长度：假设数组为
arr，长度为n。 - 外层循环控制轮数：需要进行
n-1轮比较（因为每轮确定一个元素的位置，最后一个元素自然有序）。 - 内层循环比较相邻元素：每轮中，从第一个元素开始，依次比较相邻元素（
arr[j]和arr[j+1]），如果arr[j] > arr[j+1]，则交换位置。 - 优化提前终止：如果某一轮没有发生任何交换，说明数组已完全有序，可提前结束排序。
三、代码示例（Python）¶
下面用 Python 实现冒泡排序，并结合示例数组验证效果。代码分为两步：定义排序函数，以及测试排序效果。
def bubble_sort(arr):
n = len(arr)
# 外层循环控制轮数（最多n-1轮）
for i in range(n - 1):
swapped = False # 标记本轮是否有交换
# 内层循环比较相邻元素，每轮减少一次比较（最后i个元素已排好序）
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
# 交换元素
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True # 标记发生交换
# 如果本轮没有交换，说明数组已有序，提前终止
if not swapped:
break
return arr
# 测试冒泡排序
test_arr = [5, 3, 8, 4, 2]
print("排序前：", test_arr)
sorted_arr = bubble_sort(test_arr)
print("排序后：", sorted_arr)
输出结果：
排序前： [5, 3, 8, 4, 2]
排序后： [2, 3, 4, 5, 8]
四、冒泡排序的优化与复杂度分析¶
- 优化提前终止：通过
swapped标记，如果某一轮没有交换，直接跳出循环，避免不必要的比较。 - 时间复杂度：
- 最坏情况（完全逆序）：需要n-1 + n-2 + ... + 1 = n(n-1)/2 ≈ O(n²)次比较和交换。
- 最好情况（已排序）：仅需一轮比较（无交换），时间复杂度O(n)。 - 空间复杂度：仅需要常数级额外空间（交换元素），因此空间复杂度
O(1)。
五、总结¶
冒泡排序是最简单的排序算法之一，核心思想是通过重复交换相邻元素，将大元素“冒泡”到末尾。它的优点是实现简单、易于理解，缺点是时间复杂度较高，适合小规模数据排序。如果你刚开始学习排序算法，冒泡排序是非常好的入门选择，能帮助你理解排序的基本逻辑！