一、算法核心原理“是什么”与“为什么快”快速排序之所以“快”在于它的分区操作能在一次遍历中将一个元素基准放到最终位置上同时让左右两侧满足大小关系。相比于希尔排序的“逐渐逼近”快排采用的是递归分割策略——每次都将问题规模减半因此平均深度仅为 log₂n。二、经典 C 实现Lomuto 分区法最易理解的写法这是面试中最推荐手撕的版本逻辑直观不易出错。核心是维护一个i指针指向“小于等于基准的区域的末尾”。#include iostream #include vector using namespace std; // 分区函数将 arr[low..high] 分区返回基准元素的最终下标 int partition(vectorint arr, int low, int high) { int pivot arr[high]; // 选最右边的元素作为基准 int i low - 1; // i 指向小于等于 pivot 的区域的最后一个位置 for (int j low; j high; j) { // 当前元素小于等于基准时将其与 i1 位置交换扩大小于区域 if (arr[j] pivot) { i; swap(arr[i], arr[j]); } } // 最后将基准放到中间位置i1 swap(arr[i 1], arr[high]); return i 1; // 返回基准的最终位置 } // 快速排序递归主函数 void quickSort(vectorint arr, int low, int high) { if (low high) { int pi partition(arr, low, high); // pi 是基准的索引 quickSort(arr, low, pi - 1); // 递归排左边 quickSort(arr, pi 1, high); // 递归排右边 } }三、核心优劣分析面试必答优势 1极佳的缓存局部性。分区操作是在原数组上顺序遍历对 CPU 缓存极其友好常数因子远小于归并排序和堆排序。优势 2原地排序In-place。除了递归栈开销不需要额外的大块内存不像归并需要 O(n) 辅助空间。致命短板最坏情况当数组已经有序正序或逆序且每次选最后一个元素作基准时分区极度不平衡递归深度变为 n时间复杂度退化为O(n²)。四、工程级优化策略加分项展示深度为了防止最坏情况C 的std::sort内省排序混用了快排并加入了保险机制。面试手撕时你可以主动提出以下几种优化三数取中Median-of-Three不选固定端而是取low、mid、high三个位置的中位数作为基准极大降低遇到有序数组时退化的概率。int mid low (high - low) / 2; if (arr[mid] arr[low]) swap(arr[mid], arr[low]); if (arr[high] arr[low]) swap(arr[high], arr[low]); if (arr[high] arr[mid]) swap(arr[high], arr[mid]); swap(arr[mid], arr[high]); // 将中位数放到 high 位置作为 pivot小区间插入排序当子数组长度小于阈值如 10~15时递归开销过大直接改用插入排序。随机化基准int pivot arr[low rand() % (high - low 1)];从概率上规避最坏情况。五、总结速查手撕必用Lomuto 分区法代码短。面试亮点主动说出“快排是不稳定的”、“有序数组会让它变慢需要三数取中优化”。工程警告写业务代码永远不要手写快排请直接调用std::sort因为它是内省排序已经内置了上述所有优化。资源推荐《C八股文》2026版贪心算法
