快速排序详解：原理、C++实现与优化技巧-开发者社区

快速排序详解：原理、C++实现与优化技巧

在排序算法的“江湖”中，快速排序绝对是“明星算法”——它以O(n log n)的平均时间复杂度、原地排序的特性，成为实际开发中最常用的排序方案之一。无论是面试高频考点，还是工程实践需求，掌握快速排序的原理与实现都至关重要。今天，我们就从核心思想出发，一步步拆解快速排序的逻辑，实现基础版C++代码，再探讨进阶优化技巧，让你彻底搞懂快速排序。

一、快速排序的核心思想：分治 + 基准划分

快速排序的核心灵感来自“分治法”——把一个大问题拆解成多个小问题，逐个解决后再合并结果。具体到排序上，核心步骤可以概括为3句话：

选基准：从待排序数组中选一个元素作为“基准”（pivot）；
做划分：重新排列数组，把所有比基准小的元素放到基准左边，比基准大的元素放到基准右边（相等元素可左可右），这个过程叫“分区（partition）”；
递归求解：对基准左边和右边的两个子数组，重复上面的选基准和划分步骤，直到子数组的长度为1（此时子数组已有序）。

举个通俗的例子：要给数组 [5, 2, 9, 1, 5, 6] 排序，先选基准（比如第一个元素5），分区后得到 [2, 1, 5, 5, 9, 6]（基准5在中间，左边都小于等于5，右边都大于等于5），再分别递归排序左边 [2,1] 和右边 [9,6]，最终得到有序数组。

关键特点：

原地排序：不需要额外的数组空间（仅递归调用需要栈空间），空间复杂度O(log n)（递归栈深度）；
不稳定排序：相等元素的相对位置可能改变（比如两个5，分区后位置可能互换）；
时间复杂度：平均O(n log n)，最坏O(n²)（基准选得极差时，如有序数组选第一个元素作基准），最好O(n log n)。

二、核心步骤拆解：分区（partition）算法

快速排序的核心是“分区”操作——如何高效地将数组按基准划分成左右两部分。最经典、最易实现的分区方式是“Hoare分区法”（快速排序发明者提出），此外还有“ Lomuto分区法”“三数取中法”等优化方案。我们先从最基础的Hoare分区法讲起。

1. Hoare分区法（左右指针法）

核心逻辑：用两个指针（left指向数组左端，right指向数组右端），从两端向中间遍历，找到需要交换的元素，最终确定基准的正确位置。

具体步骤（以升序排序为例）：

选数组第一个元素作为基准pivot；
left指针从左向右移动，直到找到第一个大于等于pivot的元素；
right指针从右向左移动，直到找到第一个小于等于pivot的元素；
如果left ≤ right，交换两个指针指向的元素；
重复步骤2-4，直到left > right；
交换基准元素和right指针指向的元素，此时right指针的位置就是基准的最终位置（基准左边都≤基准，右边都≥基准）。

示例演示（数组 [5, 2, 9, 1, 5, 6]，pivot=5）：

初始left=0，right=5；
left移动：找到第一个≥5的元素（5，索引0）；
right移动：找到第一个≤5的元素（6？不，继续左移，5（索引4）≤5）；
left=0 ≤ right=4，交换索引0和4的元素，数组变为 [5, 2, 9, 1, 5, 6]（两个5交换，无变化）；
left继续右移到1（元素2<5，继续），到2（元素9≥5）；right继续左移到3（元素1≤5）；
left=2 ≤ right=3，交换索引2和3的元素，数组变为 [5, 2, 1, 9, 5, 6]；
left继续右移到3（元素9≥5）；right继续左移到2（元素1≤5），此时left=3 > right=2，停止遍历；
交换基准（索引0）和right（索引2）的元素，数组变为 [1, 2, 5, 9, 5, 6]，基准5的最终位置是2。

2. Lomuto分区法（前后指针法）

另一种更直观的分区方式，核心逻辑：用一个指针i标记“小于基准区域”的右边界，再用一个指针j遍历数组，找到小于基准的元素，就放到i的右边，扩大“小于基准区域”。

具体步骤（升序排序，选最后一个元素作基准）：

选数组最后一个元素作为基准pivot；
初始化i = left - 1（i指向“小于基准区域”的最后一个元素，初始无元素）；
j从left遍历到right-1：
如果nums[j] ≤ pivot，i++，交换nums[i]和nums[j]（将当前元素加入“小于基准区域”）；
遍历结束后，交换nums[i+1]和nums[right]（将基准放到“小于基准区域”和“大于基准区域”中间），此时i+1就是基准的最终位置。

Lomuto分区法代码更简洁，但交换次数通常比Hoare分区法多，效率稍低，适合初学者理解。

三、基础版快速排序C++实现（Hoare分区法）

基于Hoare分区法，我们实现最基础的快速排序，步骤：先实现分区函数，再实现递归排序函数。

1. 代码实现

#include<iostream>#include<vector>usingnamespacestd;// Hoare分区法：返回基准的最终位置intpartition(vector<int>&nums,intleft,intright){// 选第一个元素作为基准intpivot=nums[left];inti=left;// 左指针intj=right;// 右指针while(i<j){// 右指针向左移，找到第一个 ≤ pivot 的元素while(i<j&&nums[j]>pivot){j--;}// 左指针向右移，找到第一个 ≥ pivot 的元素while(i<j&&nums[i]<=pivot){i++;}// 交换两个指针指向的元素if(i<j){swap(nums[i],nums[j]);}}// 交换基准和j指针指向的元素，确定基准最终位置swap(nums[left],nums[j]);returnj;// 返回基准位置，用于递归划分左右子数组}// 快速排序主函数：递归排序左右子数组voidquickSort(vector<int>&nums,intleft,intright){// 递归终止条件：子数组长度≤1if(left>=right){return;}// 分区，得到基准位置intpivotPos=partition(nums,left,right);// 递归排序左子数组（基准左边）quickSort(nums,left,pivotPos-1);// 递归排序右子数组（基准右边）quickSort(nums,pivotPos+1,right);}// 测试函数intmain(){vector<int>nums={5,2,9,1,5,6};cout<<"排序前：";for(intnum:nums){cout<<num<<" ";}cout<<endl;quickSort(nums,0,nums.size()-1);cout<<"排序后：";for(intnum:nums){cout<<num<<" ";}cout<<endl;return0;}

2. 代码说明

分区函数partition：接收数组引用和左右边界，返回基准的最终位置，核心是左右指针的移动和元素交换；
排序函数quickSort：递归终止条件是left ≥ right（子数组有序），否则分区后递归排序左右子数组；
原地排序：通过引用传递数组，直接修改原数组元素，无需额外空间；
测试结果：运行后输出排序前：5 2 9 1 5 6 排序后：1 2 5 5 6 9，符合预期。

3. Lomuto分区法实现（简洁版）

如果觉得Hoare分区法指针移动逻辑复杂，可先实现Lomuto分区法，代码更简洁：

// Lomuto分区法：选最后一个元素作基准intlomutoPartition(vector<int>&nums,intleft,intright){intpivot=nums[right];// 基准选最后一个元素inti=left-1;// 小于基准区域的右边界for(intj=left;j<right;j++){// 找到小于等于基准的元素，加入小于区域if(nums[j]<=pivot){i++;swap(nums[i],nums[j]);}}// 基准放到最终位置swap(nums[i+1],nums[right]);returni+1;}// 快速排序主函数（调用Lomuto分区）voidquickSortLomuto(vector<int>&nums,intleft,intright){if(left>=right)return;intpivotPos=lomutoPartition(nums,left,right);quickSortLomuto(nums,left,pivotPos-1);quickSortLomuto(nums,pivotPos+1,right);}

四、基础版的问题：优化方向（避免最坏情况）

基础版快速排序的最大问题是“基准选择不当”——如果每次选的基准都是当前子数组的最大值或最小值（比如对有序数组 [1,2,3,4,5] 选第一个元素作基准），分区后会出现“一边倒”的情况（一个子数组长度为n-1，另一个为0），此时时间复杂度会退化为O(n²)。

针对这个问题，有3个核心优化方向：优化基准选择、处理重复元素、尾递归优化。

1. 优化基准选择：三数取中法

核心思路：不选第一个或最后一个元素，而是从“左、中、右”三个位置中选中间值作为基准，避免选到极值。

实现步骤：

计算中间索引mid = left + (right - left) / 2（避免溢出，比 (left+right)/2 更安全）；
比较nums[left]、nums[mid]、nums[right]，选中间值；
将中间值交换到left位置（复用Hoare分区法的基准选择逻辑）。

优化后的分区函数（加入三数取中）：

// 三数取中：返回左、中、右三个位置的中间值索引intmedianOfThree(vector<int>&nums,intleft,intright){intmid=left+(right-left)/2;// 比较三个数，排序后取中间值if(nums[left]>nums[mid])swap(nums[left],nums[mid]);if(nums[left]>nums[right])swap(nums[left],nums[right]);if(nums[mid]>nums[right])swap(nums[mid],nums[right]);// 此时mid位置是中间值，交换到left位置作为基准swap(nums[left],nums[mid]);returnleft;}// 优化后的Hoare分区法（三数取中选基准）intoptimizedPartition(vector<int>&nums,intleft,intright){// 三数取中选基准medianOfThree(nums,left,right);intpivot=nums[left];inti=left;intj=right;while(i<j){while(i<j&&nums[j]>pivot)j--;while(i<j&&nums[i]<=pivot)i++;if(i<j)swap(nums[i],nums[j]);}swap(nums[left],nums[j]);returnj;}

三数取中法能大幅降低选到极值的概率，让时间复杂度稳定在O(n log n)，是工程实践中最常用的优化手段。

2. 处理重复元素：三路快排

当数组中有大量重复元素时（比如 [2,1,3,2,2,5,2]），基础版快速排序会把重复元素都分到基准的一侧，导致分区不平衡。三路快排的思路是将数组分成三部分：小于基准、等于基准、大于基准，仅递归排序“小于”和“大于”的部分，“等于”的部分直接有序，减少递归次数。

三路快排核心逻辑：

选基准pivot；
用三个指针：lt（小于基准区域右边界）、i（当前遍历指针）、gt（大于基准区域左边界）；
遍历数组，根据nums[i]与pivot的大小关系，将元素分到对应的区域：
- nums[i] < pivot：交换nums[i]和nums[lt+1]，lt++，i++；
- nums[i] == pivot：i++；
- nums[i] > pivot：交换nums[i]和nums[gt-1]，gt–；
遍历结束后，数组分为 [left, lt]（小于）、[lt+1, gt-1]（等于）、[gt, right]（大于），仅递归排序左右两部分。

三路快排C++实现：

voidquickSortThreeWay(vector<int>&nums,intleft,intright){if(left>=right)return;// 三数取中选基准medianOfThree(nums,left,right);intpivot=nums[left];intlt=left;// 小于基准区域的右边界（初始为left，区域为空）inti=left+1;// 当前遍历指针intgt=right+1;// 大于基准区域的左边界（初始为right+1，区域为空）while(i<gt){if(nums[i]<pivot){lt++;swap(nums[i],nums[lt]);i++;}elseif(nums[i]>pivot){gt--;swap(nums[i],nums[gt]);}else{// 等于基准，直接跳过i++;}}// 基准放到lt位置，此时[left, lt-1]<pivot，[lt, gt-1]==pivot，[gt, right]>pivotswap(nums[left],nums[lt]);// 仅递归排序小于和大于的部分quickSortThreeWay(nums,left,lt-1);quickSortThreeWay(nums,gt,right);}

三路快排在重复元素多的场景下（如排序大量重复的用户分数、商品价格），效率远高于基础版快速排序。

3. 尾递归优化：减少栈空间消耗

基础版快速排序的递归调用是“先左后右”，当数组规模很大时，递归栈深度可能达到O(n)（最坏情况），导致栈溢出。尾递归优化的思路是：递归排序较小的子数组，用循环处理较大的子数组，减少递归栈深度。

优化后的快速排序函数：

voidquickSortTailRecursion(vector<int>&nums,intleft,intright){while(left<right){// 用循环代替右子数组的递归intpivotPos=optimizedPartition(nums,left,right);// 递归排序较小的子数组，减少栈深度if(pivotPos-left<right-pivotPos){quickSortTailRecursion(nums,left,pivotPos-1);left=pivotPos+1;// 循环处理较大的右子数组}else{quickSortTailRecursion(nums,pivotPos+1,right);right=pivotPos-1;// 循环处理较大的左子数组}}}

优化后，递归栈深度稳定在O(log n)，避免了栈溢出风险，同时保持了原有的时间复杂度。

五、快速排序的性能分析与适用场景

1. 性能指标对比

排序版本	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	适用场景
基础版（Hoare）	O(n log n)	O(n²)	O(log n)（递归栈）	不稳定	小规模、无大量重复元素的数组
优化版（三数取中）	O(n log n)	接近O(n log n)（极难出现O(n²)）	O(log n)	不稳定	大多数场景（工程首选）
三路快排	O(n log n)	O(n log n)	O(log n)	不稳定	大量重复元素的数组

2. 适用场景

大规模无序数组：平均O(n log n)的时间复杂度，效率高于冒泡排序、插入排序等O(n²)算法；
对空间开销敏感的场景：原地排序特性，仅需O(log n)的递归栈空间；
不要求稳定性的场景：如排序整数、浮点数等基础类型（相等元素位置不影响结果）。

3. 不适用场景

已排序或接近有序的数组（基础版）：需用三数取中优化；
要求稳定排序的场景：如排序自定义对象（需保留相等元素的相对位置），此时应选归并排序；
小规模数组：递归调用有额外开销，此时插入排序效率可能更高（C++ STL的sort函数在子数组长度较小时会切换到插入排序）。

六、常见问题与注意事项

数组越界问题：指针移动时要确保i < j（Hoare分区法），避免访问数组外的内存；计算中间索引用mid = left + (right - left)/2，避免left + right溢出；
重复元素导致的分区不平衡：基础版在重复元素多时效率低，建议用三路快排；
递归栈溢出：大规模数组用尾递归优化，或手动实现迭代版快速排序；
基准选择不当：优先用三数取中，避免选第一个或最后一个元素（有序数组场景）；
C++ STL的sort函数：STL的sort并非纯快速排序，而是“快速排序+插入排序+堆排序”的混合实现（ introsort），综合了各算法的优势，性能更稳定，实际开发中优先使用STL的sort（如sort(nums.begin(), nums.end())）。