排序算法的速度美学：快速排序深度漫游
目录
一、快速排序思想
快速排序的核心思想是分治策略，简单来说就是 “分而治之”，它通过三步实现高效排序：
1、选基准：从待排序数组中选择一个元素作为「基准值」（pivot）。
2、分区操作：遍历数组，将小于基准值的元素放到基准值左侧，大于基准值的元素放到右侧，等于基准值的元素可在任意一侧。这一步结束后，基准值会被放到最终排序的正确位置。
3、递归排序子区间：对基准值左侧和右侧的两个子数组，重复执行 “选基准→分区” 的步骤，直到所有子数组的长度为 0 或 1（此时子数组已有序）。
思想本质
快速排序的高效性，正是源于「分区」这一步：它通过一次遍历就将一个大问题拆分成了两个规模更小的子问题，而子问题的排序可以独立进行，无需额外的合并操作。这种 “拆分为小问题→独立解决→自然合并” 的思路，是分治思想的典型体现。
二、Hoare版本
1、Hoare版本介绍
Hoare 版本是快速排序的经典原地分区实现，由算法发明者 Tony Hoare 提出，核心是双指针相向遍历。
核心步骤：
针对升序排序：首先选取区间首元素作为基准值 key，然后右指针从右向左寻找首个小于 key 的元素，左指针再从左向右寻找首个大于 key 的元素，交换两指针指向的元素并重复此过程，直到两指针相遇，最后将基准值与相遇位置的元素交换，即可完成分区（分区后基准左侧均小于 key、右侧均大于 key）。
特点：原地分区、无额外空间开销，但需遵循「右指针先行」规则，否则会导致基准归位错误。
2、编码实操
void QuickSort1(int* a, int left, int right) { // 递归终止条件：区间元素个数≤1时，无需排序直接返回 if (left >= right) { return; } // 初始化指针：begin/end遍历区间，keyi标记基准值初始位置（选左端点为基准） int begin = left; int end = right; int keyi = left; // 双指针相向遍历，完成区间分区（升序排序） while (begin < end) { // 右指针从后往前找：第一个比基准值小的元素 while (begin < end && a[end] >= a[keyi]) { end--; } // 左指针从前往后找：第一个比基准值大的元素 while (begin < end && a[begin] <= a[keyi]) { begin++; } // 交换找到的两个元素，让小值到左、大值到右 swap(&a[begin],&a[end]); } // 指针相遇时，该位置就是基准值的最终位置，交换归位 swap(&a[keyi],&a[begin]); keyi = begin; // 递归处理基准值左右两侧的子区间，完成整体排序 QuickSort1(a, left, keyi - 1); QuickSort1(a, keyi + 1, right); }问题1：为什么left 和 right指定的数据和key值相等时不能交换？
3、时间复杂度分析
这张图展示的是快速排序在最优情况下的时间复杂度推导：每次划分都能将数组均匀分成两部分，递归树会有 logN 层，且每一层都需要处理约 N 个元素，总的时间复杂度为 O(NlogN)
有些同学可能会疑惑，为啥每层遍历的元素都是 N？实际上每层遍历的元素个数是 N 减去该层基准值的数量，但基准值数量相对于 N 是低阶项，在大 O 表示法中可以忽略不计，因此我们仍认为每层总遍历元素数约为 N
那如果数组是有序的情况还能达到均分吗？显而易见，不能
但是在实际中我们会对快排进行优化，让其能近似达到一个平衡二叉树的状态
4、有序情况优化
4.1 随机选keyi
void QuickSort1(int* a, int left, int right) { //递归结束条件 // >：只有一个元素 // =：没有元素 if (left >= right) { return; } int begin = left; int end = right; int keyi = left; //优化1：随机选keyi int randi = left + rand() % (right - left + 1); swap(&a[randi], &a[keyi]); //处理[begin end]区间 //当 begin 和 end 指针相遇时，就找到了基准值 key 最终应该放置的位置 while (begin < end) { //右边找小：升序 while (begin < end && a[end] >= a[keyi]) { end--; } //左边找大：升序 while (begin < end && a[begin] <= a[keyi]) { begin++; } //找到后交换 swap(&a[begin],&a[end]); } //走到这代表begin和end当前位置就是 key 的合适位置 swap(&a[keyi],&a[begin]); keyi = begin; //递归子区间 //[left keyi - 1] keyi [keyi + 1 right] QuickSort1(a,left,keyi - 1); QuickSort1(a,keyi + 1, right); }即使输入是有序数组，随机选基准也能大概率避免 “每次选到最左 / 最右元素”，让递归树尽可能平衡，将最坏时间复杂度 O(n2) 优化为概率上的 O(nlogn)。
4.2 三数取中
int GetMidNumi(int* a,int left,int right) { int midi = (right + left)/2; if (a[left] < a[midi]) { if (a[right] < a[left]) { return left; } else if (a[right] > a[midi]) { return midi; } else { return right; } } else //a[left] > a[midi] { if (a[right] > a[left]) { return left; } else if(a[midi] > a[right]) { return midi; } else { return right; } } } void QuickSort1(int* a, int left, int right) { //递归结束条件 // >：只有一个元素 // =：没有元素 if (left >= right) { return; } int begin = left; int end = right; int keyi = left; //优化2：三数取中 int midi = GetMidNumi(a,left,right); swap(&a[midi], &a[keyi]); //处理[begin end]区间 //当 begin 和 end 指针相遇时，就找到了基准值 key 最终应该放置的位置 while (begin < end) { //右边找小：升序 while (begin < end && a[end] >= a[keyi]) { end--; } //左边找大：升序 while (begin < end && a[begin] <= a[keyi]) { begin++; } //找到后交换 swap(&a[begin],&a[end]); } //走到这代表begin和end当前位置就是 key 的合适位置 swap(&a[keyi],&a[begin]); keyi = begin; //递归子区间 //[left keyi - 1] keyi [keyi + 1 right] QuickSort1(a,left,keyi - 1); QuickSort1(a,keyi + 1, right); }这段代码为快速排序实现了三数取中优化，核心是通过 GetMidNumi 函数从区间的左、中、右三个位置中选出数值居中的元素下标，将其交换到区间左端点作为基准值，以此避免在有序数组中选到极值导致的性能退化，让递归树更接近平衡，从而将时间复杂度稳定在 O(NlogN)。
小贴士：
随机选基准和三数取中可避免快排在有序数组下的性能退化，二选一即可；但面对大量重复数据时效率仍会下降，后续将介绍三路划分来解决这一问题。
5、稳定性分析
由于快排在分区过程中会进行跨位置的交换操作（例如 swap(&a[cur], &a[prev])），这会打乱相等元素的相对位置，因此快速排序是不稳定的排序算法。
三、挖坑法
1、挖坑法介绍
挖坑法快排（以升序为例）的核心思路是：先选一个基准值并把它的位置设为第一个 “坑”，然后用右指针从后向前找比基准值小的元素填入左坑，左指针再从前向后找比基准值大的元素填入右坑，不断形成新坑，直到双指针相遇，最后把基准值填入最终的坑位完成分区，再递归排序左右子区间。
如果是降序排序，只需调整指针查找条件：右指针找比基准值大的元素，左指针找比基准值小的元素即可。
2、编码实操
void QuickSort2(int* a, int left, int right) { if (left >= right) { return; } //基准值 int key = a[left]; //坑 int hole = left; //区间控制 int begin = left; int end = right; //随机选keyi优化 int randi = left + (rand() % (right - left + 1)); swap(&a[randi],&a[hole]); //相等就表示已经为Key找到合适的坑位了 while (begin < end) { //右边先走，找小 while (begin < end && key <= a[end]) { end--; } a[hole] = a[end]; hole = end; //左边后走，找大 while (begin < end && key >= a[begin]) { begin++;; } a[hole] = a[begin]; hole = begin; } //让基准值入坑 a[hole] = key; //[left hole - 1] hole [hole + 1 right] //递归子区间 QuickSort2(a, left, hole - 1); QuickSort2(a,hole + 1,right); } 四、lomuto前后指针版本
1、前后指针版本介绍
Lomuto 前后指针版快排（以升序为例）的核心思路是：先选一个基准值，初始时 prev 和 cur 指向同一位置，然后用 cur 指针从左向右遍历，遇到比基准值小的元素时，prev 右移一位并交换二者位置；遇到比基准值大的元素时，cur 直接右移。遍历结束后，交换 prev 与基准值的位置完成分区，再递归排序左右子区间。
如果是降序排序，只需调整指针查找条件：cur 指针找比基准值大的元素即可。
2、编码实操
void QuickSort3(int* a, int left, int right) { if (left >= right) { return; } int keyi = left; //prev 从头开始的设计，是为了让遍历结束时，它刚好标记出基准值应处的位置 int prev = left; int cur = left+1; int randi = left + (rand() % (right - left + 1)); swap(&a[randi], &a[keyi]); while (cur <= right) { //cur找到了小于key的值 if (a[cur] < a[keyi]) { prev++; swap(&a[prev],&a[cur]); cur++; } else { cur++; } } swap(&a[prev],&a[keyi]); keyi = prev; //[left keyi - 1] keyi [keyi + 1 right] QuickSort3(a, left ,keyi-1); QuickSort3(a, keyi+1 ,right); } 
3、小区间优化
在快速排序中，小区间优化是一种常见的优化策略。当递归到小区间时，继续使用快速排序可能会因为递归调用的开销而导致性能下降。此时采用插入排序等简单排序算法来处理小区间，能减少递归深度和调用次数，降低栈空间的使用，同时利用插入排序在小规模数据上的优势，从而提高快速排序的综合性能。
void InsertSort(int* a,int n) { for (int i = 0;i < n - 1;i++) { int end = i; int tmp = a[i+1]; while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end]; end--; } else { break; } } a[end + 1] = tmp; } } void QuickSort3(int* a, int left, int right) { if (left >= right) { return; } //小区间优化 if ((right - left + 1) < 15) { InsertSort(a+left, right - left + 1); return; } int keyi = left; //prev 从头开始的设计，是为了让遍历结束时，它刚好标记出基准值应处的位置 int prev = left; int cur = left+1; int randi = left + (rand() % (right - left + 1)); swap(&a[randi], &a[keyi]); while (cur <= right) { //cur找到了小于key的值 if (a[cur] < a[keyi]) { prev++; swap(&a[prev],&a[cur]); cur++; } else { cur++; } } swap(&a[prev],&a[keyi]); keyi = prev; //[left keyi - 1] keyi [keyi + 1 right] QuickSort3(a, left ,keyi-1); QuickSort3(a, keyi+1 ,right); } 小区间优化的大小一般设置为 10~20（行业通用经验值，最常用的是 15）
五、迭代版本（非递归）
1、递归的缺陷
递归版快排虽逻辑清晰，但存在函数调用开销与递归深度过大导致的栈溢出风险；因此可通过手动维护栈来模拟递归调用，实现非递归版本，这也是快排非递归实现的主流方式。
2、非递归思路
非递归快排的核心思路：用栈模拟递归调用，先压入整个数组的边界，然后循环弹出边界、分区，再把左右子区间的边界压入栈，直到栈为空，排序完成。
3、编码实操
void QuickSortNonR(int* a,int left, int right) { stack st; STInit(&st); //入[left right]区间 //先入right是为了能正确取到[left right]区间 STPush(&st,right); STPush(&st,left); while (!STEmpty(&st)) { int begin = STTop(&st); STPop(&st); int end = STTop(&st); STPop(&st); //小区间优化 if (end - begin + 1 < 15) { InsertSort(a + begin,end - begin + 1); continue; } //随机选keyi int randi = begin + (rand()%(end - begin + 1)); swap(&a[randi],&a[begin]); //前后指针版本 int keyi = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { if (a[cur] < a[keyi]) { prev++; swap(&a[cur],&a[prev]); cur++; } else { cur++; } } swap(&a[prev],&a[keyi]); keyi = prev; //子区间处理 //[begin keyi - 1] keyi [keyi + 1 end] if (begin < keyi - 1) { STPush(&st, keyi - 1); STPush(&st, begin); } if(keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi + 1); } } STDestroy(&st); } 六、三路划分
1、三路划分思想
三路划分思想：把数组一次分成小于基准、等于基准、大于基准三部分，等于基准的元素直接就位不再递归，只递归左右两区，大量重复数据时效率极高，可直接替代普通快排。
2、编码实操
void QuickSortT(int* a, int left, int right) { if (left >= right) { return; } //小区间优化 if ((right - left + 1) < 15) { InsertSort(a + left,right - left + 1); return; } int begin = left; int end = right; int cur = left + 1; //随机选keyi int randi = left + (rand() % (right - left + 1)); swap(&a[randi],&a[left]); int key = a[left]; while (cur <= end) { if (a[cur] > key) { swap(&a[cur],&a[end]); end--; //不能直接++cur是因为从尾部交换过来的值我们还没检查过 } else if (a[cur] < key) { swap(&a[begin],&a[cur]); begin++; //cur可以直接++是因为begin的值已经被我们检查过了 cur++; } else { cur++; } } //[left begin - 1] [begin end] [end + 1 right] QuickSortT(a,left,begin - 1); QuickSortT(a,end + 1, right); }3、普通快排和三路划分效率对比
| 数据场景 | 三路划分时间复杂度 | 普通快排时间复杂度 |
|---|---|---|
| 全重复值（如全 2） | O(n) | O(n²) |
| 大量重复值（如 80% 是 2） | 接近 O (n) | O(nlogn)~O(n²) |
| 无重复值（随机数组） | O(nlogn) | O(nlogn) |
