快速排序 Quick Sort

交换排序 · 实践中最快的通用排序

什么是快速排序

快速排序是「分而治之」的代表：挑一个基准 pivot，把数组重排成「比它小的都在左、比它大的都在右」——这一步叫分区（partition），做完后 pivot 就落到了它最终该在的位置。然后对左右两段各自递归重复。它平均只要 O(n log n)、而且原地不吃额外内存、常数因子小，是大多数语言标准库通用排序的底子。

它怎么做

本页用 Lomuto 分区（取区间末位当 pivot）+ 一个显式区间栈代替递归：栈里存「待处理的区间」，每次弹出一段做分区、把 pivot（品红柱）换到正确位置钉死，再把左右两个子区间压回栈。点「下一步」看 [7, 6, 5, 10, 9, 8, 4, 3, 2, 1]：右侧区间栈显示还有哪些段待排，主轨上 pivot 一次次归位、绿色就位块逐渐铺满。

复杂度与适用

平均 O(n log n)、原地、不稳定。软肋是最坏 O(n²)——当 pivot 每次都取到极值（如对已有序数组取末位），分区会退化成一头沉。实战用「随机 / 三数取中」选 pivot 来规避。另外大量重复元素也会拖慢它——这正是三路快排要解决的。

看懂本页的单轴分区后，去三路快排和双轴快排页看它在真实世界怎么被打磨——同样的 lt/i/gt 指针，玩法各不相同。