快速排序作为面试高频考点、工程中常用的排序算法核心优势是平均时间复杂度O(nlogn)效率远超冒泡、插入排序。最近整理了标准递归版快排挖坑法的代码结合自己的理解做了逐行拆解、原理梳理还有针对性优化方案分享给正在啃算法的小伙伴一起吃透快排先放一份可直接运行的完整代码基于C语言也是我们今天的核心分析对象后续所有解析都围绕这份代码展开分区函数Partitionint Partition(int arr[], int left, int right) { //0.assert assert(arr ! NULL left right); //1.将这个处理范围内的第一个值作为基准值拷贝到tmp中 int tmp arr[left]; //2.进入while循环循环条件是左右指针还未相遇 while (left right) { //3.先从右向左找找比基准值小或等于的值扔到左边坑位上 while (left right arr[right] tmp) { right--; } //内部while循环退出情况1: if (left right) { arr[left] arr[right]; left; } //4.再从左向右找找比基准值大的值扔到右边坑位上 while (left right arr[left] tmp) { left; } if (left right) { arr[right] arr[left]; right--; } } //5.当while退出说明left和right相遇了此时可以将基准值tmp挪回去 arr[left] tmp; return left; }递归函数与对外接口//快速排序的递归函数 void Quick(int arr[], int left, int right) { if (left right) return; int par Partition(arr, left, right); //处理左边 Quick(arr, left, par - 1); //处理右边 Quick(arr, par 1, right); } //快排递归实现 void QuickSort(int arr[], int len) { if (arr NULL || len 1) return; Quick(arr, 0, len - 1); }测试程序// 辅助函数打印数组用于测试 void PrintArray(int arr[], int len) { for (int i 0; i len; i) { printf(%d , arr[i]); } printf(\n); } // 测试主函数 int main() { int arr[] {4, 3, 5, 1, 2, 7, 6, 9, 8}; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); PrintArray(arr, len); QuickSort(arr, len); printf(排序后); PrintArray(arr, len); return 0; }一、快排原理快速排序的核心是「分治法」简单来说就是“选一个基准分左右两区递归处理”三步走选基准从当前区间中选一个元素作为“基准值”我们的代码中选的是区间第一个元素做分区将区间内所有元素与基准值比较调整位置最终实现「左区 ≤ 基准值右区 基准值」并返回基准值的最终下标递递归以基准值下标为分界分别对左区和右区重复上述两步直到所有区间都有序区间内只有0个或1个元素。补充3个关键特性面试常考代码注释里也有提及这里再重点强调时间复杂度平均O(nlogn)最优情况最坏O(n²)数组完全有序/逆序时空间复杂度O(logn)递归栈的开销递归深度为logn稳定性不稳定相同元素的相对位置可能被改变比如数组[2,2,1]排序后可能变成[1,2,2]但两个2的原始顺序会变化。二、逐行解析代码我们的代码用的是快排中最易理解的「挖坑法」核心逻辑集中在Partition分区函数下面逐模块拆解新手也能看懂。1. 分区函数 Partition快排的核心函数作用对[left, right]区间进行分区返回基准值的最终下标是整个快排的“灵魂”拆解如下断言assert防止传入空指针arr NULL或非法区间left right提升代码健壮性实际开发中建议保留基准值 tmp arr[left]选当前区间第一个元素作为基准同时把这个位置“挖空”后续用其他元素填充外层while循环left right只要左右指针没相遇就持续进行“找元素、填坑”的操作右指针向左找循环条件left right arr[right] tmp目的是找到第一个≤基准值的元素找到后填充到左边的坑位然后左指针右移形成新坑左指针向右找循环条件left right arr[left] ≤ tmp目的是找到第一个基准值的元素找到后填充到右边的坑位然后右指针左移形成新坑基准值填坑当左右指针相遇时这个位置就是基准值的最终位置将tmp填入返回该下标用于后续递归分区。2. 递归函数 Quick分治实现这个函数很简单核心是“递归终止分区递归处理左右区间”递归终止条件left ≥ right此时区间内只有0个或1个元素已经有序直接返回int par Partition(...)调用分区函数得到基准值下标par递归左区间Quick(arr, left, par - 1)处理基准值左边的所有元素递归右区间Quick(arr, par 1, right)处理基准值右边的所有元素。3. 对外接口 QuickSort简化调用给用户提供一个简洁的调用入口无需关注left和right的初始值只需传入数组和长度即可边界判断空指针arr NULL或数组长度≤1无需排序直接返回调用递归函数Quick(arr, 0, len - 1)初始区间是整个数组从0到len-1。三、代码优化解决最坏情况提升效率我们的原版代码虽然正确但存在一个明显问题固定选区间第一个元素作为基准当数组完全有序/逆序时效率会暴跌到O(n²)此时每次分区都只能分成“1个元素剩余元素”的区间递归深度变成n。结合注释中提到的“数据越有序效率越低优化把数据打乱”再补充2个更实用的优化方案彻底解决这个问题。优化1三数取中法解决基准值选择不合理问题核心思路不固定选第一个元素而是选“left、mid、right”三个位置的中间值作为基准避免有序数组时的分区失衡。新增三数取中函数修改Partition函数开头代码如下// 新增三数取中函数返回基准值的下标 int GetMid(int arr[], int left, int right) { int mid left (right - left) / 2; // 避免溢出等价于(left right)/2 // 比较三个位置的元素返回中间值的下标 if (arr[left] arr[mid]) { if (arr[mid] arr[right]) return mid; else if (arr[left] arr[right]) return right; else return left; } else { if (arr[mid] arr[right]) return mid; else if (arr[left] arr[right]) return right; else return left; } } // 修改Partition函数开头加入三数取中 int Partition(int arr[], int left, int right) { assert(arr ! NULL left right); // 三数取中找到中间值下标交换到left位置保持后续挖坑逻辑不变 int midIdx GetMid(arr, left, right); int tmp arr[left]; arr[left] arr[midIdx]; arr[midIdx] tmp; // 后续代码不变... }优化2小区间插入排序减少递归开销核心思路当递归到“区间长度≤10”时改用插入排序。因为小区间内插入排序的效率并不比快排低还能减少递归调用的开销递归次数减少。新增插入排序函数修改Quick递归函数代码如下// 新增插入排序用于小区间优化 void InsertSort(int arr[], int left, int right) { for (int i left 1; i right; i) { int tmp arr[i]; int j i - 1; while (j left arr[j] tmp) { arr[j 1] arr[j]; j--; } arr[j 1] tmp; } } // 修改Quick递归函数加入小区间优化 void Quick(int arr[], int left, int right) { if (left right) return; // 小区间优化区间长度≤10用插入排序 if (right - left 1 10) { InsertSort(arr, left, right); return; } int par Partition(arr, left, right); Quick(arr, left, par - 1); Quick(arr, par 1, right); }优化3打乱数组简单直接适配原版代码如果不想修改太多代码也可以直接在排序前打乱数组避免数组有序导致的效率暴跌适合快速验证优化效果#include stdlib.h #include time.h // 新增打乱数组函数 void ShuffleArray(int arr[], int len) { srand((unsigned int)time(NULL)); // 设置随机种子 for (int i len - 1; i 0; i--) { int randIdx rand() % (i 1); // 生成0~i的随机下标 // 交换arr[i]和arr[randIdx] int tmp arr[i]; arr[i] arr[randIdx]; arr[randIdx] tmp; } } // 在main函数中排序前调用打乱函数 int main() { int arr[] {4, 3, 5, 1, 2, 7, 6, 9, 8}; int len sizeof(arr) / sizeof(arr[0]); printf(排序前); PrintArray(arr, len); ShuffleArray(arr, len); // 打乱数组 QuickSort(arr, len); printf(排序后); PrintArray(arr, len); return 0; }四、常见问题面试高频考点结合代码和原理整理几个新手常踩的坑和面试常问的问题帮大家避坑Q为什么快排不稳定A比如数组[2,2,1]选第一个2作为基准分区后左区是[1]右区是[2]排序后两个2的原始顺序被改变因此不稳定Q最坏时间复杂度O(n²)什么时候出现A基准值每次都是区间内的最值比如有序数组选第一个元素作为基准每次分区都只能分一个元素Q空间复杂度O(logn)来自哪里A递归栈的开销平均递归深度是logn每次分区都分成两半最坏情况递归深度是n此时空间复杂度O(n)Q挖坑法和前后指针法的区别A挖坑法更易理解核心是“挖空-填坑”前后指针法更简洁核心是“双指针交换”两者效率相近面试时掌握一种即可。五、总结我们今天分析的递归版快排挖坑法是最基础也最易掌握的快排实现代码逻辑清晰、可直接运行适合新手入门。核心要点回顾快排核心分治法 基准值分区代码核心Partition挖坑分区 Quick递归分治优化关键解决基准值选择不合理的问题三数取中、打乱数组减少递归开销小区间插入排序面试重点时间/空间复杂度、稳定性、最坏情况及优化方案。如果是面试准备建议掌握原版代码优化方案能手动写出完整代码并讲解原理如果是实际开发可根据数据量选择优化版本大数据量建议加三数取中和小区间优化。