排序
同样是排序，不同算法在时间、空间和稳定性上的取舍差别很大。下面列出 6 种常见排序算法的复杂度和稳定性，最后附一张对比表。
1. 冒泡排序（Bubble Sort）
- 时间复杂度:
- 最坏情况: O(n²)
- 平均情况: O(n²)
- 最好情况: O(n)（当数组已经有序时）
- 空间复杂度: O(1)（原地排序）
- 稳定性: 稳定
- 描述: 冒泡排序是一种简单的排序算法，通过重复遍历待排序的元素，比较相邻的元素并交换顺序错误的元素，将较大的元素“冒泡”到数组的末尾。由于其时间复杂度较高，通常不适用于大规模数据的排序。
2. 选择排序（Selection Sort）
- 时间复杂度:
- 最坏情况: O(n²)
- 平均情况: O(n²)
- 最好情况: O(n²)
- 空间复杂度: O(1)（原地排序）
- 稳定性: 不稳定
- 描述: 选择排序通过不断选择未排序部分的最小（或最大）元素，并将其放到已排序部分的末尾。实现简单，但数据量一大就很慢。
3. 插入排序（Insertion Sort）
- 时间复杂度:
- 最坏情况: O(n²)
- 平均情况: O(n²)
- 最好情况: O(n)（当数组已经有序时）
- 空间复杂度: O(1)（原地排序）
- 稳定性: 稳定
- 描述: 插入排序通过构建一个有序的子序列，将每个新的元素插入到该子序列中的正确位置。适合于小规模数据和部分有序的数据排序。
4. 快速排序（Quick Sort）
- 时间复杂度:
- 最坏情况: O(n²)（当选择的基准元素导致极端不平衡时）
- 平均情况: O(n log n)
- 最好情况: O(n log n)
- 空间复杂度: O(log n)（递归栈空间）
- 稳定性: 不稳定
- 描述: 快速排序采用分治策略，通过选择一个基准元素将数组分成两个子数组，并递归地排序子数组。平均表现好，但基准选得不好时会退化到 O(n²)。
5. 归并排序（Merge Sort）
- 时间复杂度:
- 最坏情况: O(n log n)
- 平均情况: O(n log n)
- 最好情况: O(n log n)
- 空间复杂度: O(n)（需要额外的空间来存储临时数组）
- 稳定性: 稳定
- 描述: 归并排序使用分治策略将数组分成两部分，分别排序这两部分，然后合并已排序的部分。三种情况都是 O(n log n)，代价是要用 O(n) 额外空间做合并。
6. 堆排序（Heap Sort）
- 时间复杂度:
- 最坏情况: O(n log n)
- 平均情况: O(n log n)
- 最好情况: O(n log n)
- 空间复杂度: O(1)（原地排序）
- 稳定性: 不稳定
- 描述: 堆排序基于堆数据结构，将待排序的数组构建成一个最大堆（或最小堆），然后逐步将堆顶元素移到数组的末尾。适合需要对数据进行原地排序的场景。
算法对比总结
| 排序算法 | 时间复杂度（最坏） | 时间复杂度（平均） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序 | O(n²) | O(n log n) | O(n log n) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
没有全场景最优的选择。数据基本有序时，插入排序接近 O(n)；要稳定且不在乎额外内存，用归并排序；内存紧张就选堆排序这类原地算法。