"""
气泡排序
"""
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))下面为你详细解释这段Python代码的含义、实现原理、用途以及注意事项。
### 1. 代码含义
这段代码实现了一个经典的排序算法——**气泡排序（Bubble Sort，也常译作冒泡排序）**。它接收一个数字列表 arr，通过多次遍历列表，比较相邻的两个元素，如果它们的顺序错误（前一个比后一个大），就交换它们的位置。最终将列表从小到大排序，并打印排序后的结果。
### 2. 实现原理
气泡排序的核心思想是：**像水中的气泡一样，较大的元素会通过交换逐渐“浮”到数组的末尾。**
具体步骤拆解如下：
* n = len(arr)：获取数组的长度。
* **外层循环 for i in range(n):**：控制排序的轮数。对于长度为 n 的数组，最多需要进行 n-1 轮排序。每完成一轮，就会有一个最大的元素被移动到正确的位置。
* **内层循环 for j in range(0, n - i - 1):**：控制每轮比较的次数。
* 为什么上限是 n - i - 1？因为经过 i 轮排序后，数组末尾的 i 个元素已经是有序且最大的了，不需要再参与比较，所以每轮需要比较的元素数量会逐渐减少。
* **比较与交换 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]**：如果前一个元素大于后一个元素，则交换它们的位置。Python 支持这种多元赋值语法，无需引入临时变量即可完成交换。
### 3. 用途
* **教学演示**：气泡排序逻辑极其简单直观，是初学者理解排序算法、数组遍历和元素交换的绝佳入门案例。
* **小规模数据排序**：当数据量非常小（如少于10个元素）时，气泡排序的简单性使得它的实际表现并不差。
* **近乎有序的数据**：如果数据基本有序，配合下文提到的“提前退出优化”，气泡排序的效率可以接近 $O(n)$。
### 4. 注意事项
* **时间复杂度较高**：
最坏和平均时间复杂度均为 *$O(n^2)$**，这意味着当数据量很大时，排序速度会非常慢，因此**不适用于大规模数据的排序**。
* 最好时间复杂度为 $O(n)$（在优化后的版本中）。
* **空间复杂度**：为 **$O(1)$**，因为排序是在原数组上直接修改的，只需要常数级的额外空间（属于原地排序算法）。
* **稳定性**：气泡排序是一种**稳定**的排序算法。即当数组中有相等的元素时，经过排序后相等元素的相对顺序不会改变（因为只有 > 时才交换== 时不动）。
* **优化建议（提前退出机制）**：你提供的代码即使数组在中途已经完全有序，也会傻傻地跑完所有的循环。可以增加一个 flag 标志位来优化：如果在一轮遍历中没有发生任何交换，说明数组已经有序，可以直接提前结束排序。
**优化后的代码示例：**
```python
"""
气泡排序（优化版）
"""
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False # 标志位：记录本轮是否发生了交换
for j in range(0, n - i - 1):
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 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_optimized(arr))