当前位置：首页 > news >正文

C++ 快速排序（Quick Sort）深度精讲：分治思想、Lomuto 分区法及三数取中优化，面试手撕必会

news 2026/7/5 14:35:25

一、算法核心原理（“是什么”与“为什么快”）

快速排序之所以“快”，在于它的分区操作能在一次遍历中将一个元素（基准）放到最终位置上，同时让左右两侧满足大小关系。

相比于希尔排序的“逐渐逼近”，快排采用的是递归分割策略——每次都将问题规模减半，因此平均深度仅为 log₂n。

二、经典 C++ 实现：Lomuto 分区法（最易理解的写法）

这是面试中最推荐手撕的版本，逻辑直观，不易出错。核心是维护一个i指针，指向“小于等于基准的区域的末尾”。

#include <iostream> #include <vector> using namespace std; // 分区函数：将 arr[low..high] 分区，返回基准元素的最终下标 int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; // 选最右边的元素作为基准 int i = low - 1; // i 指向小于等于 pivot 的区域的最后一个位置 for (int j = low; j < high; j++) { // 当前元素小于等于基准时，将其与 i+1 位置交换，扩大小于区域 if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } // 最后将基准放到中间位置（i+1） swap(arr[i + 1], arr[high]); return i + 1; // 返回基准的最终位置 } // 快速排序递归主函数 void quickSort(vector<int>& 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