数据结构——排序算法（简单篇：冒泡排序、选择排序、插入排序）

1️⃣ 冒泡排序（Bubble Sort）

基本思想

• 重复地比较相邻的两个元素，如果顺序错误就交换它们。
• 一趟冒泡结束后，最大（或最小）的元素会“浮”到末尾。
• 下一趟时可以少比较一次，因为最后的元素已经排好。

过程示例（升序）

假设数组：[5, 3, 8, 4, 2]

第一趟比较：

• (5, 3) → 交换 → [3, 5, 8, 4, 2]
• (5, 8) → 不换 → [3, 5, 8, 4, 2]
• (8, 4) → 交换 → [3, 5, 4, 8, 2]
• (8, 2) → 交换 → [3, 5, 4, 2, 8] ✅ 最大的 8 已到末尾

第二趟比较（不用管最后的 8）：

• (3, 5) → 不换
• (5, 4) → 交换 → [3, 4, 5, 2, 8]
• (5, 2) → 交换 → [3, 4, 2, 5, 8] ✅ 次大值 5 已到倒数第二位

… 直到全部有序。

时间复杂度

• 最坏情况：O(n²)（逆序）
• 最好情况：O(n)（已排序，可加优化）
• 空间复杂度：O(1)

Python 代码

def 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

# 示例
data = [5, 3, 8, 4, 2]
print(bubble_sort(data))

2️⃣ 选择排序（Selection Sort）

基本思想

• 每一趟从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。
• 每趟交换次数固定为 1 次，但比较次数较多。

工作过程示例（升序）

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

第一趟：

• 在 [5, 3, 8, 4, 2] 中找到最小值 2
• 交换 2 和第一个元素 → [2, 3, 8, 4, 5]

第二趟：

• 在 [3, 8, 4, 5] 中最小值 3（不动） → [2, 3, 8, 4, 5]

第三趟：

• 在 [8, 4, 5] 中最小值 4
• 交换 → [2, 3, 4, 8, 5]

第四趟：

• 在 [8, 5] 中最小值 5
• 交换 → [2, 3, 4, 5, 8]

时间复杂度

• 最坏情况：O(n²)
• 最好情况：O(n²)（比较次数固定）
• 空间复杂度：O(1)

Python 代码

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 示例
data = [5, 3, 8, 4, 2]
print(selection_sort(data))

3️⃣ 插入排序（Insertion Sort）

基本思想

• 将数组分为已排序区和未排序区。
• 每次从未排序区取出一个元素，插入到已排序区的合适位置。

工作过程示例（升序）

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

第一步（i=1）：

• 已排序区 [5]
• 取 3，插入到 5 前面 → [3, 5, 8, 4, 2]

第二步（i=2）：

• 已排序区 [3, 5]
• 取 8，放到末尾 → [3, 5, 8, 4, 2]

第三步（i=3）：

• 已排序区 [3, 5, 8]
• 取 4，插到 5 前面 → [3, 4, 5, 8, 2]

第四步（i=4）：

• 已排序区 [3, 4, 5, 8]
• 取 2，插到最前面 → [2, 3, 4, 5, 8]

时间复杂度

• 最坏情况：O(n²)
• 最好情况：O(n)（已排序）
• 空间复杂度：O(1)
• 对小规模数据或基本有序数据非常快

Python 代码

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # 当前要插入的元素
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 后移
            j -= 1
        arr[j + 1] = key
    return arr

# 示例
data = [5, 3, 8, 4, 2]
print(insertion_sort(data))

🔍 对比总结