排序是算法面试中出现频率最高的话题之一。这里系统梳理常见排序算法的思想、复杂度和适用场景。
算法对比
| 算法 | 时间（平均） | 时间（最坏） | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ |
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✅ |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ |
快速排序
核心思想：分治。选一个基准值，把数组分成小于和大于基准的两部分，递归排序。
function quickSort(arr: number[]): number[] {
if (arr.length <= 1) return arr
const pivot = arr[Math.floor(arr.length / 2)]
const left = arr.filter(x => x < pivot)
const mid = arr.filter(x => x === pivot)
const right = arr.filter(x => x > pivot)
return [...quickSort(left), ...mid, ...quickSort(right)]
}
归并排序
核心思想：先拆后合。将数组不断二分直到单元素，再两两合并有序数组。
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
return merge(left, right)
}
function merge(a: number[], b: number[]): number[] {
const result: number[] = []
let i = 0, j = 0
while (i < a.length && j < b.length) {
result.push(a[i] <= b[j] ? a[i++] : b[j++])
}
return [...result, ...a.slice(i), ...b.slice(j)]
}
选择建议
- 小规模数据（n < 50）：插入排序，常数因子小
- 通用场景：快速排序，平均性能最优
- 需要稳定排序：归并排序
- 内存受限：堆排序，O(1) 额外空间
实际工程中，编程语言内置的 sort 通常使用 TimSort（归并+插入的混合算法），已经足够高效。手写排序更多是为了理解算法思想。