冒泡排序 - 元素码农

发布时间: 2025-03-21 18:41

↑

# 冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个过程会重复进行，直到没有再需要交换的元素为止。

## 基本原理

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 重复步骤1~3，直到没有任何一对数字需要交换

## 动画演示

```
初始数组：[ 5 3 8 4 2 ]

第一轮：
[ 3 5 8 4 2 ]  // 5 > 3，交换
[ 3 5 8 4 2 ]  // 5 < 8，不交换
[ 3 5 4 8 2 ]  // 8 > 4，交换
[ 3 5 4 2 8 ]  // 8 > 2，交换

第二轮：
[ 3 5 4 2 8 ]  // 3 < 5，不交换
[ 3 4 5 2 8 ]  // 5 > 4，交换
[ 3 4 2 5 8 ]  // 5 > 2，交换
[ 3 4 2 5 8 ]  // 5 < 8，不交换

第三轮：
[ 3 4 2 5 8 ]  // 3 < 4，不交换
[ 3 2 4 5 8 ]  // 4 > 2，交换
[ 3 2 4 5 8 ]  // 4 < 5，不交换
[ 3 2 4 5 8 ]  // 5 < 8，不交换

第四轮：
[ 2 3 4 5 8 ]  // 3 > 2，交换
[ 2 3 4 5 8 ]  // 3 < 4，不交换
[ 2 3 4 5 8 ]  // 4 < 5，不交换
[ 2 3 4 5 8 ]  // 5 < 8，不交换

排序完成：[ 2 3 4 5 8 ]
```

## 代码实现

### Python实现

```python
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("排序前:", arr)
bubble_sort(arr)
print("排序后:", arr)
```

### 优化版本

```python
def optimized_bubble_sort(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("排序前:", arr)
optimized_bubble_sort(arr)
print("排序后:", arr)
```

## 性能分析

### 时间复杂度

- 最好情况：O(n)，当数组已经有序时
- 最坏情况：O(n²)，当数组逆序时
- 平均情况：O(n²)

### 空间复杂度

- O(1)，只需要一个临时变量用于交换

### 稳定性

- 稳定排序算法
- 相等元素的相对位置在排序后不会改变

## 优缺点

### 优点

1. 实现简单，容易理解
2. 不需要额外的存储空间
3. 稳定的排序算法

### 缺点

1. 时间复杂度较高，效率低
2. 交换次数过多
3. 不适合大规模数据排序

## 应用场景

1. 小规模数据排序
2. 教学演示使用
3. 几乎有序的数据排序
4. 对稳定性有要求的场景

## 实际应用示例

### 1. 成绩排序

```python
class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    
    def __str__(self):
        return f"{self.name}: {self.score}"

def sort_students(students):
    n = len(students)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if students[j].score < students[j + 1].score:
                students[j], students[j + 1] = students[j + 1], students[j]
                swapped = True
        if not swapped:
            break
    return students

# 使用示例
students = [
    Student("Alice", 85),
    Student("Bob", 92),
    Student("Charlie", 78),
    Student("David", 95),
    Student("Eve", 88)
]

print("排序前:")
for student in students:
    print(student)

sort_students(students)

print("\n按成绩降序排序后:")
for student in students:
    print(student)
```

### 2. 日期排序

```python
from datetime import datetime

def sort_dates(dates):
    n = len(dates)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if dates[j] > dates[j + 1]:
                dates[j], dates[j + 1] = dates[j + 1], dates[j]
                swapped = True
        if not swapped:
            break
    return dates

# 使用示例
dates = [
    datetime(2023, 5, 15),
    datetime(2023, 3, 10),
    datetime(2023, 7, 22),
    datetime(2023, 1, 5),
    datetime(2023, 4, 30)
]

print("排序前:")
for date in dates:
    print(date.strftime("%Y-%m-%d"))

sort_dates(dates)

print("\n按日期升序排序后:")
for date in dates:
    print(date.strftime("%Y-%m-%d"))
```

## 总结

冒泡排序是一种基础的排序算法，它的主要特点是：

1. 实现简单，易于理解和实现
2. 是稳定的排序算法
3. 时间复杂度较高，不适合大规模数据排序
4. 在特定场景（如几乎有序的数据）下有一定优势

虽然在实际应用中，冒泡排序由于其效率问题较少使用，但它对于理解排序算法的基本原理非常有帮助，也是学习其他排序算法的基础。在处理小规模数据或教学演示时，冒泡排序仍然是一个很好的选择。