复杂度对比
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 快排 | O(n log n) | O(n²) | O(log n) | 否 |
| 归并 | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排 | O(n log n) | O(n log n) | O(1) | 否 |
| 插入 | O(n²) | O(n²) | O(1) | 是 |
快速排序（三路）
def quick_sort(arr, lo, hi):
if lo >= hi: return
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
quick_sort(arr, lo, i - 1)
quick_sort(arr, i + 1, hi)选择建议
- 通用场景：快排（内存友好）
- 需要稳定：归并或 Tim Sort
- 数据量小（n < 20）：插入排序