快速排序与归并排序：深度手写
hard排序快速排序归并排序分治三路快排
快速排序：两种分区方案对比
Lomuto 分区（维护单指针 i）
// i 是「小于 pivot 区域」的右边界，j 向右扫描
int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi];
int i = lo; // i 指向下一个「小区」位置
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
swap(arr, i++, j); // 把小的放到 i，i 右扩
}
}
swap(arr, i, hi); // pivot 落到正确位置
return i;
}
优点：逻辑简单，易实现
缺点：当有大量重复元素时，仍然会把等于 pivot 的元素都放左边，导致不平衡
Hoare 分区（两端同时扫描）
比 Lomuto 平均交换次数少约 3 倍，是实际工程中更常用的版本：
int partition(int[] arr, int lo, int hi) {
int pivot = arr[lo + (hi - lo) / 2]; // 取中间作 pivot
int i = lo - 1, j = hi + 1;
while (true) {
do { i++; } while (arr[i] < pivot); // 从左找到 >= pivot 的
do { j--; } while (arr[j] > pivot); // 从右找到 <= pivot 的
if (i >= j) return j; // 交叉，分区完毕
swap(arr, i, j);
}
}
// 注意：Hoare 方案中 partition 返回 j，调用时：
void quickSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int p = partition(arr, lo, hi);
quickSort(arr, lo, p); // 注意是 p，不是 p-1
quickSort(arr, p + 1, hi);
}
三路快排：处理大量重复元素（荷兰国旗）
当数组中有大量重复元素时，普通快排每次只能排好 pivot 一个位置，效率退化。三路快排将等于 pivot 的元素全部聚在中间，一次排好所有相等的：
[3, 1, 4, 3, 5, 3, 2, 3] pivot = 3
→ [1, 2 | 3, 3, 3, 3 | 4, 5]
< pivot == pivot > pivot
void quickSort3(int[] arr, int lo, int hi) {
if (lo >= hi) return;
// 三个指针：
// lt: arr[lo..lt-1] < pivot
// gt: arr[gt+1..hi] > pivot
// i: 当前扫描位置
int pivot = arr[lo];
int lt = lo, gt = hi, i = lo + 1;
while (i <= gt) {
if (arr[i] < pivot) swap(arr, lt++, i++); // 小的放到左区
else if (arr[i] > pivot) swap(arr, i, gt--); // 大的放到右区（i 不动，还要检查换来的）
else i++; // 等于，直接后移
}
// arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
quickSort3(arr, lo, lt - 1);
quickSort3(arr, gt + 1, hi);
}
为什么 arr[i] > pivot 时 i 不能后移：把 arr[gt] 换到 i 位置后，这个新来的数还没检查过，需要重新判断。
快速排序最坏情况退化与随机化
退化场景：
- 数组已排序（升序/降序）+ Lomuto 总选末尾 → 每次分区都不平衡 → O(n²)
- 所有元素相同 + 普通二路快排 → 同样退化
解决方案：
// 方法1：随机选 pivot（最常用）
int randIdx = lo + new Random().nextInt(hi - lo + 1);
swap(arr, randIdx, hi); // 换到末尾，继续 Lomuto
// 方法2：三数取中（median-of-three）
// 选 lo、mid、hi 三个位置中值为 pivot，避免极端情况
int mid = lo + (hi - lo) / 2;
if (arr[lo] > arr[mid]) swap(arr, lo, mid);
if (arr[lo] > arr[hi]) swap(arr, lo, hi);
if (arr[mid] > arr[hi]) swap(arr, mid, hi);
int pivot = arr[mid]; // mid 是三者中位数
归并排序：原地（In-Place）实现
标准归并排序需要 O(n) 额外空间。某些极限场景有时要求减少空间使用。
方法：复用辅助数组（最常用）
int[] tmp; // 全局辅助数组，只分配一次
void mergeSort(int[] arr) {
tmp = new int[arr.length];
sort(arr, 0, arr.length - 1);
}
void sort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
sort(arr, lo, mid);
sort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
void merge(int[] arr, int lo, int mid, int hi) {
// 先把 arr[lo..hi] 复制到 tmp
for (int k = lo; k <= hi; k++) tmp[k] = arr[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) arr[k] = tmp[j++]; // 左半用完
else if (j > hi) arr[k] = tmp[i++]; // 右半用完
else if (tmp[i] <= tmp[j]) arr[k] = tmp[i++]; // 左小，取左（≤保证稳定）
else arr[k] = tmp[j++];
}
}
自底向上归并（迭代，避免递归栈溢出）
void mergeSortBottomUp(int[] arr) {
int n = arr.length;
int[] tmp = new int[n];
for (int size = 1; size < n; size *= 2) { // 子数组大小：1, 2, 4, 8...
for (int lo = 0; lo < n - size; lo += 2 * size) {
int mid = lo + size - 1;
int hi = Math.min(lo + 2 * size - 1, n - 1);
merge(arr, tmp, lo, mid, hi);
}
}
}
void merge(int[] arr, int[] tmp, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) tmp[k] = arr[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) arr[k] = tmp[j++];
else if (j > hi) arr[k] = tmp[i++];
else if (tmp[i] <= tmp[j]) arr[k] = tmp[i++];
else arr[k] = tmp[j++];
}
}
优势：无递归，不消耗调用栈，适合对栈深度敏感的场景。
归并排序应用：统计逆序对（LeetCode 315 / 剑指51）
逆序对：i < j 且 arr[i] > arr[j]。在 merge 过程中，当右半的元素 tmp[j] 被选时，左半剩余的所有元素（共 mid - i + 1 个）都与 tmp[j] 构成逆序对：
long count = 0;
void merge(int[] arr, int[] tmp, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) tmp[k] = arr[k];
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) arr[k] = tmp[j++];
else if (j > hi) arr[k] = tmp[i++];
else if (tmp[i] <= tmp[j]) arr[k] = tmp[i++];
else {
count += (mid - i + 1); // ← 关键：左半还剩 mid-i+1 个，都比 tmp[j] 大
arr[k] = tmp[j++];
}
}
}
为什么正确：归并时两个子数组已经各自有序。当 tmp[i] > tmp[j]，说明左半从 i 到 mid 的所有数都 > tmp[j]（因为左半有序），且这些数的原始下标都小于 tmp[j] 的原始下标，形成逆序对。
链表归并排序（LeetCode 148）
链表不支持随机访问，但归并排序只需要顺序访问，是最适合链表的排序算法（快排不适合链表）：
ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 快慢指针找中点
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null; // 断开链表
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
else { cur.next = l2; l2 = l2.next; }
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
时间：O(n log n)，空间：O(log n)（递归栈）
复杂度对比总结
| 算法版本 | 时间（平均） | 时间（最坏） | 空间 | 稳定 |
|---|---|---|---|---|
| 快排 Lomuto | O(n log n) | O(n²) | O(log n) | ❌ |
| 快排 三路 | O(n log n) | O(n²) | O(log n) | ❌ |
| 快排 随机化 | 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(n) | ✅ |
| 链表归并 | O(n log n) | O(n log n) | O(log n) | ✅ |