LeetCode 补充题 4. 手撕快速排序
题目描述
给定整数数组
nums，请将其按非递减顺序排列并返回，所有元素及其重复次数都要保留。本补充题沿用力扣「排序数组」的输入输出，要求手动实现快速排序，不能直接调用内置排序函数。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
-
1 <= nums.length <= 5 * 10^4。 -
-5 * 10^4 <= nums[i] <= 5 * 10^4。 - 力扣原题要求 O(n log n) 时间，并尽量减少额外空间。
- 随机快速排序的 O(n log n) 为期望时间，最坏仍可能退化为 O(n²)，下文会区分这两种情况。
题意分析
手写快速排序，把整数数组按从小到大的顺序排列并返回。排序只改变元素的位置，所有元素及其重复次数都要保留，不能直接调用库中的排序函数。
下面的实现直接在原数组中交换元素，不另外创建数组保存分区；递归调用仍然需要栈空间。重点是如何把当前区间分好，再对尚未有序的部分继续排序。
解法：随机基准 + 三路分区
核心思路
[!blue]
从当前区间随机选一个元素，将它的值保存为基准
pivot。把区间分成小于、等于、大于基准的三段后，中间一段的值完全相同，已经不需要排序；只要再把左右两段各自排好，整个区间就有序了。这就是快速排序的分治过程。用
lt标记等值段的起点，i扫描尚未分类的元素，gt标记未知区间的末尾。在当前处理的[left, right]内，lt左侧都小于基准，lt到i - 1都等于基准，i到gt尚未分类，gt右侧都大于基准。当前值小于基准，就与
lt位置交换，并同时右移lt和i：换回来的值属于等值段，或者只是与自身交换，不需要再检查。当前值大于基准，就与gt位置交换并左移gt，但不能移动i，因为从右侧换来的值还没有分类。当前值等于基准，只需右移i。当
i > gt时，未知区间清空，[lt, gt]就是完整的等值段。递归时跳过它，可以避免反复处理重复值；随机选择基准则减少划分表现对原始排列的依赖，但不保证每次都能均匀划分。
解题步骤
- 若
left >= right，区间最多只有一个元素，直接返回。- 在
[left, right]中随机选取并保存基准值，初始化lt = i = left、gt = right。- 在
i <= gt时分类：小于基准就与lt交换并右移lt、i；大于基准就与gt交换并只左移gt；等于基准就只右移i。- 分区结束后，递归排序
[left, lt - 1]和[gt + 1, 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[java.util.concurrent.ThreadLocalRandom.current().nextInt(left, right + 1)];
// 四段依次为小于、等于、未知、大于基准，未知区间是 i 到 gt。
int lt = left;
int i = left;
int gt = right;
while (i <= gt) {
if (nums[i] < pivot) {
swap(nums, lt++, i++);
} else if (nums[i] > pivot) {
// 右端换回的元素尚未分类，因此本轮不增加 i。
swap(nums, i, gt--);
} else {
i++;
}
}
quickSort(nums, left, lt - 1);
quickSort(nums, gt + 1, right);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
import "math/rand"
func sortArray(nums []int) []int {
var quickSort func(int, int)
quickSort = func(left, right int) {
if left >= right {
return
}
// 基准保存为值，后续交换不会改变本轮比较基准。
pivot := nums[left+rand.Intn(right-left+1)]
// 四段依次为小于、等于、未知、大于基准，未知区间是 i 到 gt。
lt, i, gt := left, left, right
for i <= gt {
if nums[i] < pivot {
nums[lt], nums[i] = nums[i], nums[lt]
lt++
i++
} else if nums[i] > pivot {
// 右端换回的元素尚未分类，因此本轮不增加 i。
nums[i], nums[gt] = nums[gt], nums[i]
gt--
} else {
i++
}
}
quickSort(left, lt-1)
quickSort(gt+1, right)
}
quickSort(0, len(nums)-1)
return nums
}
复杂度分析
- 时间复杂度：期望 $O(n \log n)$。每次分区线性扫描当前区间，随机基准使划分在期望意义下较均衡，递归各层的总扫描量不超过 $O(n)$，期望层数为 $O(\log n)$。若连续出现极不均衡划分，最坏仍为 $O(n^2)$；全相等数组只需一轮 $O(n)$ 分区。
- 空间复杂度：递归栈期望 $O(\log n)$，最坏 $O(n)$；分区本身只用常数空间。
关键点总结
[!green]
- 基准保存为值：交换会改变原来的位置，比较对象必须保持不变。
- 等值段无需递归：重复元素越集中，跳过等值段省去的重复比较越多。
- 右侧交换后继续检查当前位置：换回的值尚未分类，不能直接跳过。
易错点总结
[!yellow]
- 与
gt交换后不能递增i：否则会漏掉换入元素。- 递归区间排除等值段：边界应为
lt - 1和gt + 1，避免重复处理甚至不收敛。- 随机基准不保证最坏情况消失：仍可能连续产生不均衡划分，不能把最坏时间写成 $O(n \log n)$。
- 先判断区间长度再抽取基准：空数组或单元素区间应直接返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 215. 数组中的第K个最大元素 | 中等 | 快速选择复用分区，但只递归包含第k项的一侧，本题要排序两边。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！