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 = Trueif not swapped:breakreturn 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 = ifor j in range(i + 1, n):if arr[j] < arr[min_idx]:min_idx = jarr[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 - 1while j >= 0 and arr[j] > key:arr[j + 1] = arr[j]  # 后移j -= 1arr[j + 1] = keyreturn arr# 示例
data = [5, 3, 8, 4, 2]
print(insertion_sort(data))

🔍 对比总结

算法	最好时间	最坏时间	稳定性	空间复杂度	适用场景
冒泡排序	O(n)	O(n²)	稳定	O(1)	数据量小，且大致有序
选择排序	O(n²)	O(n²)	不稳定	O(1)	数据量小，对交换次数敏感
插入排序	O(n)	O(n²)	稳定	O(1)	数据基本有序，小规模排序