LeetCode 补充题 4. 手撕快速排序
目录
题目描述
题意分析
输入是一个整型数组，要求把它就地重排成升序并返回。题面里没有额外的辅助数组预算，也没有「保持相等元素原有先后」的要求，所以不必追求稳定性，可以放心地跨位置交换元素。
约束条件透露了两个信号。第一，元素是整数而不是抽象的可比较对象，比较只有
<、>、==三种结果，这意味着「等于」是一个可以被单独利用的分类，而不是可以随便并到某一侧的杂项。第二，题目要求现场手写而不是调库，说明考点不是「能不能排好」，而是「能不能把一趟线性重排的边界和不变量说清楚」——判分点全在指针推进和递归区间上。需要提前想清楚的边界情形有：空数组与单元素数组（
length - 1会得到-1，递归入口必须能接住这种区间）；所有元素相等（最容易把某些写法卡成死循环或退化成逐个剥离）；已经升序或已经降序（会暴露基准选择的好坏）；只有两个元素（区间短到中点和端点重合，最容易触发「递归区间没变小」的错误）；以及含负数和重复值的一般输入。这几类用例后面每一节都会反复用到。
解法：双向分区快速排序
核心思路
选择中间元素作为基准，左指针寻找不小于基准的元素，右指针寻找不大于基准的元素，交换后继续收缩。分区结束后，递归排序左右两段。
指针移动必须发生在交换之后，否则遇到大量等于基准的元素时会停滞。
解题步骤
- 区间长度小于 2 时返回。
- 取中间元素为
pivot，初始化i = left、j = right。i、j分别向内寻找需要交换的元素；当i <= j时交换并继续移动。- 分别递归
[left, j]和[i, right]。
代码实现
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivot = nums[left + (right - left) / 2];
int i = left, j = right;
while (i <= j) {
while (nums[i] < pivot) {
i++;
}
while (nums[j] > pivot) {
j--;
}
if (i <= j) {
int temp = nums[i];
nums[i++] = nums[j];
nums[j--] = temp;
}
}
quickSort(nums, left, j);
quickSort(nums, i, right);
}
}
func sortArray(nums []int) []int {
var quickSort func(int, int)
quickSort = func(left, right int) {
if left >= right {
return
}
pivot := nums[left+(right-left)/2]
i, j := left, right
for i <= j {
for nums[i] < pivot {
i++
}
for nums[j] > pivot {
j--
}
if i <= j {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}
quickSort(left, j)
quickSort(i, right)
}
quickSort(0, len(nums)-1)
return nums
}
复杂度分析
- 时间复杂度：平均 $O(n \log n)$，分区持续极端失衡时最坏 $O(n^2)$。
- 空间复杂度：平均 $O(\log n)$，最坏 $O(n)$，来自递归栈。
关键点总结
- 中间元素作基准可避免有序数组在常见场景下持续单边分区。
- 分区结束后递归
[left, j]和[i, right]。- 该实现原地排序，不保证稳定性。
易错点总结
- 交换后忘记同时移动
i、j，重复值会导致死循环。- 递归边界写成原区间，导致无限递归。
- 空数组调用时必须由
left >= right直接返回。- 快速排序最坏仍是 $O(n^2)$，不能写成严格 $O(n \log n)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 912. 排序数组 | 中等 | 同一个判题入口，但不限定写法，可以用归并或堆排序绕开快排的最坏情况 |
| 215. 数组中的第K个最大元素 | 中等 | 只要第 k 大，分区后只递归包含目标下标的那一侧，期望代价降到线性 |
| 973. 最接近原点的 K 个点 | 中等 | 比较键是距离而不是元素本身，分区只需前 k 个而不必整体有序 |
| 75. 颜色分类 | 中等 | 值域只有三个取值，一次三路分区就排完，完全不需要递归 |
| 324. 摆动排序 II | 中等 | 目标不是升序而是大小穿插，要先用分区找到中位数再重排 |
| 148. 排序链表 | 中等 | 链表无法随机访问，取不到中点基准，只能改用自底向上归并 |
| 88. 合并两个有序数组 | 简单 | 两段已经有序，做的是归并里的合并步骤，不涉及分区 |