快速排序是实践中综合性能最强的通用排序算法被称为「排序算法之王」核心基于分治思想 分区操作通过递归不断缩小问题规模在绝大多数场景下效率远超其他同复杂度排序算法。一、核心思想与分治逻辑快速排序的本质是「基准定位 分而治之」从数组中选一个元素作为基准pivot执行分区操作把所有小于基准的元素移到基准左边所有大于基准的元素移到基准右边操作完成后基准直接落在它最终排序的正确位置上递归对基准左侧、右侧的两个子数组重复上述操作直到子数组长度为 1天然有序整个过程像用标杆把数组一次次 “劈开” 成两半因此也被形象称为「标杆劈叉法」。二、核心流程分步详解快速排序的核心是分区Partition分区的实现方式直接决定代码写法和效率行业内有两种经典分区方案霍尔分区双指针两端法和洛穆托分区单指针遍历法。2.1 方案一霍尔分区Hoare Partition双指针法这是快排发明者霍尔提出的原始方案也是最常用、交换次数最少的实现采用左右双指针从两端向中间逼近。分区步骤演示以数组[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]为例选左端点 6 作为基准完整分区过程如下初始化左指针left指向数组首元素右指针right指向数组尾元素保存基准值pivot 6右指针左移从右往左找第一个小于基准的数从末尾 8 开始86、106、56 → 右指针停在索引 7元素 5将右指针的值 5 赋值给左指针位置数组变为[5, 1, 2, 7, 9, 3, 4, 5, 10, 8]左指针右移从左往右找第一个大于基准的数从开头 5 开始56、16、26、76 → 左指针停在索引 3元素 7将左指针的值 7 赋值给右指针位置数组变为[5, 1, 2, 7, 9, 3, 4, 7, 10, 8]重复上述两步左右指针不断向中间收缩右指针继续左移找到 4索引 6赋值给左指针位置 →[5, 1, 2, 4, 9, 3, 4, 7, 10, 8]左指针继续右移找到 9索引 4赋值给右指针位置 →[5, 1, 2, 4, 9, 3, 9, 7, 10, 8]右指针继续左移找到 3索引 5赋值给左指针位置 →[5, 1, 2, 4, 3, 3, 9, 7, 10, 8]当左右指针相遇时left right分区结束将基准值 6 放到指针相遇的位置最终分区结果[5, 1, 2, 4, 3, 6, 9, 7, 10, 8]基准 6 已经处于最终排序的正确位置左侧全小于 6右侧全大于 6分区代码实现cpp运行// 霍尔分区返回基准元素的最终下标 int partition(vectorint nums, int left, int right) { int pivot nums[left]; // 选左端点作为基准 while (left right) { // 右指针从右往左找第一个小于基准的元素 while (left right nums[right] pivot) { right--; } nums[left] nums[right]; // 移到左指针位置 // 左指针从左往右找第一个大于基准的元素 while (left right nums[left] pivot) { left; } nums[right] nums[left]; // 移到右指针位置 } nums[left] pivot; // 基准归位 return left; // 返回基准的最终位置 }注意内层循环的判断条件必须带等号/否则遇到和基准相等的元素会陷入死循环。2.2 方案二洛穆托分区Lomuto Partition单指针法实现更简洁的分区方案选右端点作为基准用单指针遍历数组维护「小于基准的区域边界」遍历完成后将基准交换到分界处。分区步骤演示同样以数组[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]为例选右端点 8 作为基准初始化i -1表示「小于基准的区域」的右边界j 从 0 开始遍历j 遍历到小于等于基准的元素时i 右移一位交换 i 和 j 位置的元素把元素纳入小于区遍历结束后交换 i1 位置和基准位置基准归位最终基准 8 落在索引 7左侧全小于等于 8右侧全大于 8。分区代码实现cpp运行int partition(vectorint nums, int left, int right) { int pivot nums[right]; // 选右端点作为基准 int i left - 1; // 小于基准的区域的右边界 for (int j left; j right; j) { if (nums[j] pivot) { i; // 扩大小于区 swap(nums[i], nums[j]); } } swap(nums[i 1], nums[right]); // 基准归位 return i 1; }特点代码简单易写但交换次数比霍尔分区多整体效率略低。三、完整递归实现基础版分区完成后对基准左右两个子数组递归执行相同逻辑直到子数组长度 ≤ 1。cpp运行#include vector using namespace std; // 霍尔分区函数复用上面的实现 int partition(vectorint nums, int left, int right) { int pivot nums[left]; while (left right) { while (left right nums[right] pivot) right--; nums[left] nums[right]; while (left right nums[left] pivot) left; nums[right] nums[left]; } nums[left] pivot; return left; } // 快速排序主递归函数 void quickSort(vectorint nums, int left, int right) { // 递归终止条件区间为空或只有一个元素天然有序 if (left right) { return; } // 1. 分区得到基准的最终位置 int pivotPos partition(nums, left, right); // 2. 递归排序基准左侧区间 quickSort(nums, left, pivotPos - 1); // 3. 递归排序基准右侧区间 quickSort(nums, pivotPos 1, right); } // 对外调用接口 void quickSort(vectorint nums) { if (nums.empty()) return; quickSort(nums, 0, nums.size() - 1); }四、复杂度深度分析4.1 时间复杂度快速排序的时间复杂度取决于分区的均匀程度也就是基准选择的好坏。最好情况O (nlogn)每次分区都把数组均匀切成两半递归深度为 log₂n每层分区总操作量为 O (n)由主定理可推导出时间复杂度 O (nlogn)。平均情况O (nlogn)绝大多数场景下基准选择不会极端不均匀平均时间复杂度稳定在 O (nlogn)且常数因子远小于归并排序、堆排序实际运行速度最快。最坏情况O (n²)当数组已经完全有序 / 逆序且选端点作为基准时每次分区只能分出 1 个元素和 n-1 个元素递归深度为 n总操作量退化为 O (n²)。这也是基础快排的最大缺陷可以通过优化基准选择彻底避免。4.2 空间复杂度主要开销是递归调用栈最好 / 平均情况递归深度为 O (logn)最坏情况为 O (n)分区操作是原地排序不需要额外数组空间优化后尾递归优化可将最坏栈空间也控制在 O (logn)五、稳定性分析快速排序是不稳定排序。原因分区过程中元素会发生远距离交换可能打乱值相等元素的原始相对顺序。举例数组[2, 1, 1]两个 1 标记先后顺序选第一个 2 作为基准分区后结果为[1, 1, 2]原本在后面的 1 被移到了前面两个 1 的相对顺序被破坏六、经典优化方案进阶重点基础版快排在极端场景下存在性能缺陷工业级实现都会做多层优化以下是最核心的 5 种优化手段。优化 1随机选择基准解决问题避免有序数组下退化为 O (n²)。原理分区前随机选一个元素和左端点交换再以左端点为基准。彻底打破 “有序数组选端点必最坏” 的局面让 O (n²) 的概率趋近于 0。cpp运行int partition(vectorint nums, int left, int right) { // 随机选一个位置和左端点交换 int randIdx left rand() % (right - left 1); swap(nums[left], nums[randIdx]); int pivot nums[left]; // ... 后续分区逻辑不变 }优化 2三数取中法选基准解决问题比随机基准更稳定避免选到极端值作为基准。原理取区间左端点、中间点、右端点三个元素选择值为中位数的元素作为基准保证基准不会是最大 / 最小值分区更均匀。cpp运行int getMid(vectorint nums, int left, int right) { int mid left (right - left) / 2; // 让 nums[left] 成为三个数的中位数 if (nums[left] nums[right]) swap(nums[left], nums[right]); if (nums[mid] nums[right]) swap(nums[mid], nums[right]); if (nums[mid] nums[left]) swap(nums[left], nums[mid]); return nums[left]; // 此时左端点就是中位数 }优化 3小区间改用插入排序解决问题小数组下递归开销大插入排序常数因子更小、速度更快。原理当子数组长度小于阈值通常取 10~15时不再递归快排改用插入排序同时减少递归深度。cpp运行void quickSort(vectorint nums, int left, int right) { // 小区间用插入排序替代递归 if (right - left 1 10) { insertionSort(nums, left, right); return; } int pivotPos partition(nums, left, right); quickSort(nums, left, pivotPos - 1); quickSort(nums, pivotPos 1, right); }优化 4三路快速排序荷兰国旗优化解决问题数组中存在大量重复元素时普通快排会重复分区相等元素效率低下。原理将数组分成三部分小于基准、等于基准、大于基准等于基准的元素已经归位后续只递归小于和大于的区间大幅减少重复分区。cpp运行void quickSort3Way(vectorint nums, int left, int right) { if (left right) return; int pivot nums[left rand() % (right - left 1)]; int lt left - 1; // 小于区右边界 int gt right 1; // 大于区左边界 int i left; // 当前遍历指针 while (i gt) { if (nums[i] pivot) { swap(nums[lt], nums[i]); // 放入小于区 } else if (nums[i] pivot) { swap(nums[--gt], nums[i]); // 放入大于区i不移动新换过来的元素还没判断 } else { i; // 等于基准直接跳过 } } // 只递归小于和大于的区间等于区已经有序 quickSort3Way(nums, left, lt); quickSort3Way(nums, gt, right); }优化 5尾递归优化解决问题减少递归栈深度避免最坏情况栈溢出。原理每次只递归较短的那一半区间另一半用循环处理保证递归深度不超过 logn。七、常见易错点与面试考点边界死循环内层循环必须带等号且必须先移动右指针再移动左指针选左端点为基准时否则会出现越界或死循环递归范围基准已经归位递归时必须排除基准即[left, pivot-1]和[pivot1, right]溢出问题计算中间下标时用left (right - left) / 2不要用(left right) / 2避免数值溢出TopK 问题快速排序的分区思想是解决 TopK 问题的最优方案无需完全排序即可找到第 K 大 / 小的元素平均时间复杂度 O (n)非递归实现可以用栈保存每一层的左右区间模拟递归过程避免栈溢出谢谢