什么是排序？¶
在我们生活中，排序是很常见的操作。比如考试成绩排名、手机通讯录按字母排序、字典里按字母顺序查单词……本质上，排序就是将一组无序的数据，按照特定规则（比如从小到大、从大到小）重新排列的过程。在计算机科学中，排序算法是最基础也最核心的算法之一，掌握排序算法能帮助我们更高效地处理数据。
什么是冒泡排序？¶
冒泡排序（Bubble Sort）是最简单的排序算法之一，它的名字来源于“气泡”——就像水中的气泡会向上浮一样，冒泡排序中较大的元素会通过交换逐渐“冒”到数组的末尾。
举个例子：如果有一组数字 [5, 3, 8, 4, 2]，我们要将它们从小到大排序。冒泡排序的过程就像这样：每一轮都会把当前未排序部分的“最大气泡”（最大元素）“推”到末尾，直到所有元素都排好序。
冒泡排序的核心思路¶
以 [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 已经“冒”到了末尾，现在未排序部分是 [3, 5, 4, 2]。
第二轮（确定第二大元素）¶
未排序部分长度减1（去掉末尾的 8），继续比较相邻元素：
- 比较 3 和 5：3 < 5，不交换
- 比较 5 和 4：5 > 4，交换 → [3, 4, 5, 2]
- 比较 5 和 2：5 > 2，交换 → [3, 4, 2, 5]
结果：第二大元素 5 已“冒”到倒数第二位置，未排序部分是 [3, 4, 2]。
第三轮（确定第三大元素）¶
未排序部分长度继续减1，继续比较：
- 比较 3 和 4：3 < 4，不交换
- 比较 4 和 2：4 > 2，交换 → [3, 2, 4]
结果：第三大元素 4 已“冒”到倒数第三位置，未排序部分是 [3, 2]。
第四轮（确定第四大元素）¶
未排序部分仅剩两个元素：
- 比较 3 和 2：3 > 2，交换 → [2, 3]
结果：所有元素排序完成，最终数组为 [2, 3, 4, 5, 8]。
冒泡排序的步骤总结¶
- 外层循环：控制需要进行多少轮比较。数组长度为
n时，最多需要n-1轮（因为每轮确定一个元素的位置）。 - 内层循环：每轮比较相邻元素，将较大的元素“冒泡”到末尾。每轮结束后，未排序部分长度减1（即不需要再比较已排好序的末尾元素）。
- 优化点：如果某一轮没有发生交换，说明数组已排好序，可提前终止循环（避免无效计算）。
代码实现（Python）¶
基础版本（无优化）¶
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # 外层循环：共n-1轮
for j in range(n - 1 - i): # 内层循环：每轮比较n-1-i次
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # 交换相邻元素
return arr
# 测试
arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr)) # 输出：[2, 3, 4, 5, 8]
优化版本（提前终止）¶
def optimized_bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False # 标记是否发生交换
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
# 测试（对已排序数组优化明显）
arr = [1, 2, 3, 4, 5]
print(optimized_bubble_sort(arr)) # 输出：[1, 2, 3, 4, 5]（仅需1轮即可结束）
冒泡排序的复杂度分析¶
- 时间复杂度：
- 最坏情况（完全逆序）：每轮都需交换，共需
n-1 + n-2 + ... + 1 = n(n-1)/2次比较，时间复杂度为 O(n²)。 -
最好情况（已排序）：优化版本仅需1轮（无交换），时间复杂度为 O(n)。
-
空间复杂度：仅需常数级额外空间（交换时的临时变量），空间复杂度为 O(1)（原地排序）。
冒泡排序的特点与适用场景¶
- 优点：简单易懂，实现容易，适合理解排序算法的基本思想。
- 缺点：效率较低（O(n²)），数据量大时不适用。
- 适用场景：数据量小或对效率要求不高的场景（如教学演示、简单数据排序）。
小练习¶
尝试用冒泡排序对数组 [9, 7, 6, 15, 16, 5, 10, 11] 排序，你能手动走一遍流程吗？可以参考上述步骤，写出代码验证结果。
通过以上讲解，相信你已经掌握了冒泡排序的核心逻辑。作为最基础的排序算法，冒泡排序能帮助你理解“比较交换”的思想，为学习更复杂的排序算法（如快速排序、归并排序）打下基础！