这叫 分治（Divide and Conquer）。
三、那为什么快排能“快”？
公式很经典：
平均时间复杂度：O(n logn)
最坏时间复杂度：O(n²)
关键就在选的 pivot。
如果 pivot 选得好 → 每次都能“对半分” → log n 层递归
如果 pivot 选得差 → 每次只分出一个元素 → 变成冒泡 → O(n²)
如果 pivot 选得好 → 每次都能“对半分” → log n 层递归
如果 pivot 选得差 → 每次只分出一个元素 → 变成冒泡 → O(n²)
那么问题来了：pivot 到底怎么选？
四、如果不随机，会发生什么？
有些人会写成：
pivot = nums[0]
听起来没毛病，但在真实的数据中：
如果数组本身接近有序
pivot 永远在最边上
每次只能排掉一个元素
复杂度直接从 O(n log n) 退化成 O(n²)
如果数组本身接近有序
pivot 永远在最边上
每次只能排掉一个元素
复杂度直接从 O(n log n) 退化成 O(n²)
这就是为什么：
写快排不用随机化，就是等着被面试官针对。
写快排不用随机化，就是等着被面试官针对。
因为真实业务场景中，「接近有序的数据」非常常见。
例如：日志时间戳、价格序列、用户行为轨迹……
也就是说：
不随机，快排很可能不“快”。
五、那怎么解决？
随机化！
随机化的 pivot 选择很简单：
importrandom
pivot_index = random.randint(left, right)
nums[left], nums[pivot_index] = nums[pivot_index], nums[left]
通过随机扰动，让 pivot 的位置不可预测：
能够避免“极端接近有序场景”
使得快排的 期望时间复杂度稳定为 O(n log n)
能够避免“极端接近有序场景”
使得快排的 期望时间复杂度稳定为 O(n log n)
这是工程上真实会用到的所谓 反击退化风险的手段。
六、现场手写一个？
那我们就写一个 可过所有在线评测的标准解法：
defquick_sort(nums, left, right):
ifleft >= right:
return
# 随机化 pivot
importrandom
pivot_idx = random.randint(left, right)
nums[left], nums[pivot_idx] = nums[pivot_idx], nums[left]
pivot = nums[left]
i, j = left, right
whilei < j:
# 右边先走，找比 pivot 小的
whilei < j andnums[j] >= pivot:
j -= 1
# 左边再走，找比 pivot 大的
whilei < j andnums[i] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
# pivot 放回中间
nums[left], nums[i] = nums[i], nums[left]
quick_sort(nums, left, i - 1)
quick_sort(nums, i + 1, right)
这段代码面试现场可以直接写，不翻车。
七、总结面试时怎么答得漂亮
可以这样说：
“快排的核心是分治，通过 pivot 将数组划分成左右两部分再递归。
“快排的核心是分治，通过 pivot 将数组划分成左右两部分再递归。
如果 pivot 选择不当，比如数据接近有序，会退化成 O(n²)。
如果 pivot 选择不当，比如数据接近有序，会退化成 O(n²)。
为避免退化，我们会采用随机化 pivot，让每次划分更均匀，使时间复杂度稳定在 O(n log n)。
为避免退化，我们会采用随机化 pivot，让每次划分更均匀，使时间复杂度稳定在 O(n log n)。
然后你需要我现场手写的话，我可以写标准版 + 随机化版本。”
然后你需要我现场手写的话，我可以写标准版 + 随机化版本。”
这叫在理解的基础上 会写 + 会解释 + 会设计。返回搜狐，查看更多