冒泡排序：用Python实现从小到大排序¶
你有没有想过，水中的气泡是怎么上升的？它们会从水底慢慢往上冒，较大的气泡会更快到达水面。冒泡排序的名字就来源于这个现象——它会让数组中较大的元素“冒泡”到数组的末尾。
简单来说，冒泡排序（Bubble Sort）是一种基础的排序算法。它的核心思想是：重复地走访要排序的数组，一次比较两个相邻的元素，如果它们的顺序错误就交换位置，直到整个数组有序。
冒泡排序的工作步骤¶
- 比较相邻元素：从数组第一个元素开始，依次比较相邻的两个元素（比如第1个和第2个，第2个和第3个，…）。
- 交换元素：如果前一个元素比后一个大，就交换它们的位置。
- 重复操作：重复上述步骤，直到所有元素都“冒泡”到正确的位置。每完成一轮，数组末尾的一个最大元素就会被排好序。
- 优化提前终止：如果某一轮中没有发生任何交换，说明数组已经有序，无需继续排序。
用Python实现冒泡排序¶
下面通过一个具体例子理解排序过程，并写出Python代码。假设我们要排序数组：[64, 34, 25, 12, 22, 11, 90]。
步骤分解（手动模拟）：¶
- 第1轮：比较相邻元素，最大的数（90）会“冒泡”到末尾，数组变为：
[34, 25, 12, 22, 11, 64, 90]。 - 第2轮：比较前6个元素，第二大的数（64）会“冒泡”到倒数第二位，数组变为：
[25, 12, 22, 11, 34, 64, 90]。 - 第3轮：继续比较，直到所有元素有序。
Python代码实现：¶
def bubble_sort(arr):
n = len(arr)
# 外层循环控制排序轮数（最多n-1轮）
for i in range(n - 1):
swapped = False # 标记本轮是否发生交换
# 内层循环比较相邻元素，每轮减少一次比较（末尾已排序）
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# 交换相邻元素（Python语法简化交换）
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 如果本轮无交换，说明数组已有序，提前终止
if not swapped:
break
print(f"第{i+1}轮结束：{arr}")
return arr
# 测试
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", test_arr)
sorted_arr = bubble_sort(test_arr)
print("最终排序:", sorted_arr)
代码解释：¶
-
外层循环：
for i in range(n - 1)
控制排序轮数，最多需要n-1轮（n为数组长度），因为每轮会确定一个最大元素的位置。 -
内层循环：
for j in range(0, n - i - 1)
比较相邻元素，每轮内层循环的次数比上一轮少1次（因为末尾i个元素已排好序）。 -
交换逻辑：
arr[j], arr[j + 1] = arr[j + 1], arr[j]
用Python的元组赋值语法，简洁交换相邻元素的值。 -
优化标志：
swapped
如果某轮无交换，说明数组已有序，直接终止循环，避免无效比较。
运行结果（含中间过程）：¶
原始数组: [64, 34, 25, 12, 22, 11, 90]
第1轮结束：[34, 25, 12, 22, 11, 64, 90]
第2轮结束：[25, 12, 22, 11, 34, 64, 90]
第3轮结束：[12, 22, 11, 25, 34, 64, 90]
第4轮结束：[12, 11, 22, 25, 34, 64, 90]
第5轮结束：[11, 12, 22, 25, 34, 64, 90]
最终排序: [11, 12, 22, 25, 34, 64, 90]
冒泡排序的特点¶
- 时间复杂度：最坏情况（完全逆序）为O(n²)，最好情况（已排序）为O(n)（优化后）。
- 空间复杂度：O(1)（仅需临时变量，无额外空间）。
- 稳定性：稳定排序（相等元素相对位置不变）。
总结¶
冒泡排序是最简单的排序算法之一，核心是“相邻元素比较与交换”。虽然效率较低（适合小规模数据），但理解其原理对掌握排序思想至关重要。通过Python代码实现后，你可以轻松处理简单的排序需求，或尝试优化为更高效的版本（如归并排序、快速排序）。
现在，尝试用其他数组（如[5, 3, 8, 4, 2]）测试冒泡排序，看看是否能正确输出排序结果吧！