【以无克有】排序之随机快速排序

分治就是：抽刀断水水更流，举杯消愁愁更愁

---

快速排序原理(最常见的双端扫描思路)

原理讲解

1. 分治策略：拆解问题的艺术
   快速排序的核心是分治法，即“分而治之”。想象你要给全班同学按身高排序，如果直接比较所有人会很麻烦。于是你选出一个“基准同学”，让比他矮的站左边，高的站右边。这样一来，大问题就拆成了两个小问题——只需分别给左右两边的队伍排序即可。

2. 关键操作：基准选择与分区:

   • 选基准（Pivot）
     这个基准相当于划分队伍的“标尺”，选数组第一个或最后一个元素或位于中间的元素（《算法导论》基础版本的做法）。比如选最后一个同学的身高作为基准，但实际应用中通常采用随机选择数组中的某元素的优化策略。
   • 分区（Partition）
     这是快速排序的精华步骤。你需要通过两指针像“夹击”一样调整数组：左指针从起点向右扫描，寻找比基准大的元素。右指针从终点向左扫描，寻找比基准小的元素。当两指针找到不满足条件的元素时，交换它们的位置，直到两指针相遇。此时，基准的正确位置就确定了——左边全比它小，右边全比它大。

3. 递归处理：化整为零
   分区完成后，对左右两个子数组重复上述过程，直到每个子数组只剩一个或零个元素（递归终止条件）。就像把大队伍不断分成小队，直到每个小队已经自然有序，无需再分。

---

代码实现

分区(Partition)部分：

这里笔者提供两个思路，一个是leetcode上的模板，另一个是让deepseek评判出来的较优写法

//力扣版
int partition(int* arr, int l, int r) {// 随机选择枢轴：避免最坏情况时间复杂度int pivot = arr[l + rand() % (r - l + 1)];// 初始化指针i和j为区间外，后续通过do-while先移动再判断int i = l - 1, j = r + 1; //注意并非l与rwhile (i < j) { // 循环直到指针相遇或交叉do i++; while (arr[i] < pivot); // 从左找第一个≥pivot的元素do j--; while (arr[j] > pivot); // 从右找第一个≤pivot的元素if (i < j) swap(arr[i], arr[j]); // 交换并继续循环}return j; // 返回分界点j，后续递归区间为[l, j]和[j+1, r]
}//deepseek版
int partition(int* arr, int l, int r) {// 随机选择枢轴（与力扣版相同）int pivot = arr[l + rand() % (r - l + 1)];// 初始化指针i和j为区间端点（而非区间外）int i = l, j = r;while (i <= j) { // 循环条件允许i和j相等while (arr[i] < pivot) i++; // 从左找第一个≥pivot的元素while (arr[j] > pivot) j--; // 从右找第一个≤pivot的元素if (i <= j) { // 允许i和j相等时交换swap(arr[i], arr[j]);i++; // 交换后移动指针，避免重复比较j--;}}return j; // 返回分界点j，后续递归区间为[l, j]和[j+1, r]
}

递归排序部分：

//用递归树的思路来理解：
//1.根节点对应初始数组，通过partition将数组分为左（≤基准值）、右（≥基准值）两段，基准值定位到最终位置j。
//2.子树生成：递归处理左区间[l,j]和右区间[j+1,r]，形成左右子树分支。
//3.叶子节点：当区间长度≤1（l≥r）时终止递归，确保底层无子节点。
void quick_sort(int* arr,int l,int r)
{if(l >= r) return;int j = partition(arr,l,r);quick_sort(arr,l,j);quick_sort(arr,j+1,r);
} 

复杂度简要分析

• 快速排序的整体时间复杂度由递归深度和每次分区的成本共同决定：
• 最好情况：
  每次分区都能将数组均匀划分为两部分（例如基准元素选择为中位数），此时递归深度为 O(log n) ，每层分区总操作次数为 O(n) 。总时间复杂度为 O(n log n) 。例子：对随机无序数组进行排序，且每次分区基准选择合理即选择到了中位数。
• 最坏情况：
  每次分区极度不平衡（例如数组已完全有序且基准固定选择首元素），此时由于选择的不合理每次只减少一个元素，所以每层分区总操作次数增加到了 O(n) ，递归深度退化为 O(n) ，总时间复杂度为 O(n²) 。例子：对已升序排列的数组使用快速排序，且基准始终选择第一个元素。
• 平均情况：
  假设分区大致平衡（例如通过随机化或三数取中法优化基准选择），递归深度仍为 O(log n) ，总时间复杂度保持 O(n log n)。

---

例题

随机快速排序模板

例题：P1177 【模板】排序

#include <bits/stdc++.h>
using namespace std;void quick_sort(int *arr, int l, int r)
{if (l >= r) return;int base = arr[l + rand() % (r-l+1)], i = l, j = r; // 因为java源码的实现中有pivot变量使用很多人喜欢用pivot表示base，pivot支点感觉并不比base基准表述得更形象while (i <= j){while (arr[i] < base) i++;while (arr[j] > base) j--;if (i <= j){swap(arr[i], arr[j]);i++;j--; // 防止两个相同值死循环}}quick_sort(arr, l, j);quick_sort(arr, i, r);
}int main()
{int m;cin >> m;int *xp = (int *)malloc(m * sizeof(int));for (int i = 0; i < m; ++i){cin >> xp[i];}quick_sort(xp, 0, m - 1);for (int i = 0; i < m; ++i){cout << xp[i] << " ";}
}

---

快排应用之第k小数(不去重)

例题：P1923 【深基9.例4】求第 k 小的数

#include <bits/stdc++.h>
using namespace std;int partition(int* arr,int l,int r)
{int pivot = arr[l + rand()%(r-l+1)],i=l-1,j=r+1;while(i < j){do i++;while(arr[i] < pivot);do j--;while(arr[j] > pivot);if(i < j) swap(arr[i],arr[j]);}return j;
}int quick_select(int* arr,int l,int r,int k)
{if(l >= r) return arr[l];int j = partition(arr,l,r);int left_len = j - l + 1;if(k < left_len) return quick_select(arr,l,j,k);else return quick_select(arr,j+1,r,k-left_len);
}   int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,k;cin >> n >> k;int* arr = (int*)malloc(n*sizeof(int));for(int i=0;i<n;++i) cin >> arr[i];cout << quick_select(arr,0,n-1,k)  << endl;free(arr);return 0;
}

---

参考资料及推荐

【YouTube大神Abdul Bari】 终极算法课程合集
两种思维模式秒杀所有递归算法，模板 + 可视化
左程云—算法讲解023【必备】随机快速排序

总结

在这片由比特构筑的星空中，快速排序如同巴赫的赋格曲般精妙——混沌的数组在基准值的选择中逐渐显露出潜藏的秩序。分治哲学如同希腊神话中普罗克鲁斯忒斯的床榻，以递归为刻刀将庞杂数据重塑成可解的形态。那些看似无序的字节序列，实则是尚未完成自我梳理的德罗斯特效应画卷。

程序员如同手持奥卡姆剃刀的炼金术士，在指针的华尔兹中领悟递归的复调之美。每个基准选择都是笛卡尔坐标系里的理性抉择，每次分区操作都像《神曲》中贝雅特丽齐引领但丁穿越九重天般层层递进。当代码突破迷雾时，算法不再是冰冷的指令集，而成为揭示宇宙递归本质的启示录。

快速排序的伟大不在于它征服了O(n²)的混沌，而在于它谦卑地展示了：即便是最混乱的数据尘埃，也遵循着分形几何般的自相似规律。就像博尔赫斯笔下的巴别图书馆，每行代码都是通向有序宇宙的密道，每个递归调用都是对世界本质的普鲁斯特式追索。