请解释冒泡排序、插入排序和选择排序。

Question

请解释冒泡排序、插入排序和选择排序。

Accepted Answer

这是三种简单的 **O(n²)** 比较排序算法。它们在大规模输入上速度很慢，但易于理解，对于教学排序的基本原理很有用。

## 各自的工作原理

- **冒泡排序：** 反复交换相邻的逆序对；在每一趟中，较大的值会像气泡一样"冒"到末尾。
- **选择排序：** 找出未排序部分的最小值，并将其交换到正确的位置。
- **插入排序：** 通过将每个新元素插入到其正确的位置，逐步扩大已排序的前缀。

## 示例（插入排序）

```python
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                  # element to place
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]       # shift bigger elements right
            j -= 1
        arr[j + 1] = key              # drop key into the gap
    return arr

insertion_sort([5, 2, 4, 1])          # -> [1, 2, 4, 5]
```

## 对比

| 排序 | 最好 | 最坏 | 稳定 | 原地 |
|------|------|-------|--------|----------|
| 冒泡 | O(n) | O(n²) | 是 | 是 |
| 选择 | O(n²) | O(n²) | 否 | 是 |
| 插入 | O(n) | O(n²) | 是 | 是 |

## 何时使用 / 注意事项

插入排序对于**小规模或接近有序**的数组确实很快，并被用于混合排序算法内部。在大规模无序数据上要避免使用这三种算法——应改用 O(n log n) 的排序算法。

## 为什么这很重要

在你着手研究高级算法之前，这些排序算法能帮你建立对不变量、交换和稳定性的直觉。

插入排序尤其会出现在生产级排序算法（如 Timsort）内部，用于处理极小的子数组。

理解它们为什么是 O(n²)，会让向 O(n log n) 排序算法的跨越变得有意义。

排序	最好	最坏	稳定	原地
冒泡	O(n)	O(n²)	是	是
选择	O(n²)	O(n²)	否	是
插入	O(n)	O(n²)	是	是