一句话总结
排序算法是算法面试的基础，核心考点：快排（分治+partition，平均O(nlogn)）、归并（稳定+O(n)空间，适合外部排序）、堆排序（O(1)空间+TopK问题）。记住复杂度对比表，能手写快排和归并。
排序算法概览
常见排序算法复杂度：
| 算法 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
选择建议：小数据量用插入排序，大数据量用快排或归并，需要稳定性用归并排序。
快速排序
核心思想：选取基准元素（pivot），将数组分为小于pivot和大于pivot两部分，递归排序。
function quickSort(arr, left, right) {\n if (left >= right) return;\n const pivot = partition(arr, left, right);\n quickSort(arr, left, pivot - 1);\n quickSort(arr, pivot + 1, right);\n}
优化：三数取中选pivot、小数组切换插入排序、三路快排处理大量重复元素。
归并排序
核心思想：分治法，将数组递归拆分为两半，分别排序后合并。
优势：稳定排序，时间复杂度始终O(nlogn)，适合链表排序和外部排序。
面试常考变体：
1. 计算逆序对数量
2. 合并K个有序链表
3. 计算数组中的小和
堆排序与TopK
堆排序核心：利用最大堆/最小堆的性质进行排序。
TopK问题：从N个数中找出最大/最小的K个数。
最优方案：维护一个大小为K的最小堆，遍历数组时如果元素大于堆顶则替换。时间复杂度O(nlogk)，空间复杂度O(k)。
面试变体：
1. 数据流中的中位数（大小堆）
2. 滑动窗口最大值
3. 合并K个升序链表
实战场景
场景：手写快排（面试高频）
public void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
private int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 选最左为基准
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
if (i < j) swap(arr, i, j);
}
swap(arr, left, i); // 基准归位
return i;
}
// 优化：三数取中选 pivot，避免最坏 O(n²)