Partition函数：从快排核心到算法实战，解决数组高频问题

1. 项目概述从Partition到算法实战最近在整理自己的C/C学习笔记发现关于快速排序及其衍生问题——比如“数组中出现次数超过一半的数字”和“最小的k个数”——的讨论又火了起来。这其实一点也不意外因为这些题目完美地串联起了数据结构、算法思想以及C/C核心编程技巧是检验一个程序员基本功的绝佳试金石。很多朋友在面试时都被问到过但往往只知其然不知其所以然或者代码写出来总感觉差那么点意思边界条件处理得磕磕绊绊。问题的核心都绕不开一个看似简单却威力巨大的函数Partition。它不仅是快速排序的灵魂更是解决一系列“基于位置和顺序”问题的瑞士军刀。今天我就结合自己多年的开发和面试经验把这几个问题掰开揉碎了讲清楚。我们不只讲标准答案更要深挖背后的“为什么”比如为什么Partition能用来找中位数处理重复元素时有哪些坑不同的实现方式在效率和稳定性上有什么差异我会用最直白的C代码和生活中的类比让你一次搞懂并能写出既高效又健壮的代码。无论你是正在刷题准备面试还是想巩固算法基础这篇文章都能给你带来实实在在的收获。2. Partition函数快排的灵魂与算法基石2.1 Partition的核心思想与经典实现Partition中文常译为“划分”或“分割”它的任务非常明确在一个给定的数组区间内选取一个基准值pivot然后重新排列数组使得所有小于基准值的元素都位于其左侧所有大于等于基准值的元素都位于其右侧。最终函数返回基准值在重新排列后所在的位置索引。这个操作是快速排序能够“分而治之”的关键。一次划分后基准值的位置就被确定了接下来只需要递归地对左右两个子区间进行同样的操作即可。经典的实现方式是“双指针挖坑填数法”或者叫Lomuto partition scheme它逻辑清晰易于理解和实现。// 经典的Lomuto分区方案 int Partition(vectorint nums, int left, int right) { // 选择最右侧元素作为基准值pivot int pivot nums[right]; // i指向小于pivot区域的最后一个位置 int i left - 1; // j从左到右遍历整个区间不包括pivot自身 for (int j left; j right; j) { // 如果当前元素小于pivot就把它交换到“小于区” if (nums[j] pivot) { i; // “小于区”向右扩大一位 swap(nums[i], nums[j]); // 将当前元素纳入“小于区” } } // 循环结束后i指向最后一个小于pivot的元素 // 将pivot原nums[right]交换到正确的位置i1 swap(nums[i 1], nums[right]); // 返回pivot的最终位置 return i 1; }为什么这么实现变量i维护了一个“小于pivot”的边界。j是侦察兵不断向前探索。每当j发现一个小于pivot的“好同志”就通知i把边界向后挪一位然后把这个“好同志”请到边界内。遍历完成后所有“好同志”都集中在[left, i]区间。最后把一直待在队尾的pivot请到i1这个位置它左边全是比它小的右边全是大于等于它的任务完成。注意这个实现是不稳定的。稳定性是指如果两个元素值相等排序后它们的相对位置保持不变。Lomuto方案在交换过程中可能会打乱相等元素的原始顺序。如果稳定性是需求需要考虑其他方法但通常快排不要求稳定。2.2 另一种高效实现Hoare分区法除了Lomuto方案还有一种更早由Hoare提出的分区方法通常交换次数更少效率稍高但逻辑稍微绕一点。// Hoare分区方案 int Partition_Hoare(vectorint nums, int left, int right) { int pivot nums[left]; // 选择最左侧元素为基准 int i left - 1, j right 1; // 指针初始化在区间外 while (true) { // 从左向右找到第一个大于等于pivot的元素 do { i; } while (nums[i] pivot); // 从右向左找到第一个小于等于pivot的元素 do { --j; } while (nums[j] pivot); // 如果指针相遇或交错说明划分完成 if (i j) return j; // 注意这里返回的是j // 交换这两个错位的元素 swap(nums[i], nums[j]); } }两种方法的对比与选择Lomuto方案优点逻辑简单直观代码易于编写和理解是教学和面试中的常客。缺点当数组中存在大量重复元素时容易导致不平衡的划分例如所有元素都等于pivot从而使快排退化为O(n²)。交换次数相对较多。返回值返回的是pivot的最终位置。Hoare方案优点平均交换次数更少效率略高。对于包含大量重复元素的数组表现通常更好特别是与“三数取中”法结合时。缺点逻辑稍复杂边界条件需要仔细处理。注意循环内部的do-while需要防止数组越界上述简易版假设pivot值一定在数组中。返回值返回的是划分后左子区间的右边界这个位置不一定是pivot的最终位置。在实现快排时递归区间应为[left, pos]和[pos1, right]。实操心得在面试或日常编码中如果没特别要求实现Lomuto方案即可因为它更通用也更容易解释清楚。但心里要知道Hoare方案的存在及其优劣。如果被问到如何优化包含大量重复元素的数组排序可以引出Hoare方案或更高级的“三路划分”。2.3 基准值Pivot选择的艺术Partition的性能很大程度上取决于基准值的选择。一个糟糕的基准值比如总是选最大或最小值会导致每次划分都极度不平衡使快排退化到O(n²)的时间复杂度。常见的pivot选择策略固定选择总是选择第一个或最后一个元素。这是最简单但也是最危险的方法对于已排序或逆序数组性能极差。随机选择在[left, right]区间内随机选择一个元素作为pivot然后将其与末尾或开头元素交换再执行标准Partition。这是强烈推荐的方法它能将最坏情况出现的概率降到极低实现也简单。int Partition_Random(vectorint nums, int left, int right) { // 生成[left, right]范围内的随机索引 int random_index left rand() % (right - left 1); // 将随机选中的pivot交换到末尾沿用之前的逻辑 swap(nums[random_index], nums[right]); return Partition(nums, left, right); // 调用之前的Lomuto partition }三数取中法取区间左端、右端和中间三个元素将其中值大小排在中间的那个作为pivot。这种方法能有效避免极端输入且不需要随机数生成。int GetMidIndex(vectorint nums, int left, int right) { int mid left (right - left) / 2; // 比较三个数返回中间值的索引 if ((nums[left] nums[mid] nums[mid] nums[right]) || (nums[right] nums[mid] nums[mid] nums[left])) return mid; if ((nums[mid] nums[left] nums[left] nums[right]) || (nums[right] nums[left] nums[left] nums[mid])) return left; return right; } // 使用时将选中的中位数交换到末尾 int mid GetMidIndex(nums, left, right); swap(nums[mid], nums[right]);我的建议在实际工程中随机选择通常是性价比最高的方案。它代码简单且能很好地应对各种未知的数据分布。三数取中法也是一个非常稳健的选择特别是当随机数生成有开销或需要确定性行为时。3. 基于Partition的快速排序实现理解了Partition快速排序的实现就水到渠成了。其核心就是“分治”思想通过Partition操作确定一个元素的最终位置然后递归地对左右两个子区间进行同样的操作。3.1 递归版本的实现与细节void QuickSort(vectorint nums, int left, int right) { // 递归终止条件区间内元素少于2个 if (left right) return; // 关键步骤1进行分区得到基准值位置pos // 使用随机分区以避免最坏情况 int pos Partition_Random(nums, left, right); // 关键步骤2递归排序左半部分 [left, pos-1] QuickSort(nums, left, pos - 1); // 关键步骤3递归排序右半部分 [pos1, right] QuickSort(nums, pos 1, right); } // 对外提供的接口 void QuickSort(vectorint nums) { if (nums.size() 1) return; // 初始化随机数种子 srand(time(nullptr)); QuickSort(nums, 0, nums.size() - 1); }这里有几个至关重要的细节递归终止条件if (left right) return;当区间为空left right或只有一个元素left right时无需再排序。这个条件必须正确否则会导致无限递归。递归区间分区函数返回的pos是基准值的最终正确位置。因此左子区间是[left, pos-1]右子区间是[pos1, right]。千万不要将pos再包含进任何一个子区间否则会导致死循环或错误。随机化通过Partition_Random引入随机性这是保证算法平均时间复杂度为O(n log n)的关键。3.2 时间与空间复杂度分析时间复杂度最佳/平均情况每次划分都能将数组大致平分递归树的高度为O(log n)每层需要进行O(n)次比较因此平均时间复杂度为O(n log n)。最坏情况每次划分都极度不平衡例如数组已排序且总是选择端点作为pivot递归树退化成链高度为O(n)因此最坏时间复杂度为O(n²)。随机化pivot选择就是为了让最坏情况几乎不可能发生。空间复杂度主要是递归调用栈所占用的空间。在平均情况下递归深度为O(log n)因此平均空间复杂度为O(log n)。在最坏情况下递归深度为O(n)因此最坏空间复杂度为O(n)。3.3 快速排序的优化策略虽然基础的快排已经很快但在一些特殊场景或追求极致性能时还可以进行优化小数组切换为插入排序当递归到子数组规模很小比如长度小于10时快速排序的递归开销可能比排序本身还大。此时可以切换为更简单的插入排序后者对小规模数据非常高效。void QuickSort_Optimized(vectorint nums, int left, int right) { // 优化点小区间使用插入排序 if (right - left 16) { // 阈值通常取10-20 InsertionSort(nums, left, right); return; } int pos Partition_Random(nums, left, right); QuickSort_Optimized(nums, left, pos - 1); QuickSort_Optimized(nums, pos 1, right); }尾递归优化编译器通常会自动进行尾递归优化但我们可以手动处理来减少栈深度。即先对较短的子数组进行递归较长的子数组通过循环处理。void QuickSort_TailRecursion(vectorint nums, int left, int right) { while (left right) { int pos Partition_Random(nums, left, right); // 总是先递归处理较短的区间 if (pos - left right - pos) { QuickSort_TailRecursion(nums, left, pos - 1); left pos 1; // 长的区间通过循环迭代处理 } else { QuickSort_TailRecursion(nums, pos 1, right); right pos - 1; } } }处理大量重复元素三路划分当数组中存在大量重复元素时标准的两路划分小于pivot和大于等于pivot效率不高。三路划分将数组分为“小于pivot”、“等于pivot”、“大于pivot”三部分能一次性处理好所有等于pivot的元素在重复元素多时优势明显。实操心得对于日常使用和面试掌握基础的随机化快排已经足够。但如果你在面试中被问到“如何优化快排”那么“随机化pivot”、“小数组用插入排序”和“三路划分处理重复元素”就是非常好的加分点。这体现了你对算法不仅有实现能力还有优化意识。4. Partition的妙用解决“超过一半的数字”问题4.1 问题定义与常见思路问题数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。例如数组[1, 2, 3, 2, 2, 2, 5, 4, 2]长度为9数字2出现了5次超过一半4.5因此答案是2。常见思路有几种哈希表统计法遍历数组用哈希表记录每个数字出现的次数。时间O(n)空间O(n)。排序法将数组排序中间位置的数字一定是众数。时间O(n log n)空间O(1)如果允许修改原数组。摩尔投票法最优解一次遍历时间O(n)空间O(1)。核心是“对拼消耗”。基于Partition的方法时间O(n)空间O(1)但会修改原数组。这正是我们要重点讨论的。4.2 基于Partition的算法原理这个方法的智慧在于利用了“中位数”的性质。如果一个数字出现的次数超过一半那么排序后这个数字一定会出现在数组的中间位置。更准确地说这个数字就是数组的中位数对于长度为奇数的数组是正中间对于偶数长度是中间两个的任意一个但题目保证有解所以超过一半的数必然也是中位数。因此问题转化为寻找长度为n的数组的中位数。而Partition函数正是用来寻找第k小或第k大元素的利器。算法步骤随机选择一个pivot对数组进行一次Partition操作得到其位置pos。比较pos与数组的中间位置mid n / 2。如果pos mid恭喜nums[pos]就是中位数也就是我们要找的数字。如果pos mid说明中位数在左半部分我们在[left, pos-1]区间内继续寻找。如果pos mid说明中位数在右半部分我们在[pos1, right]区间内继续寻找。重复步骤1和2直到找到pos mid。这个过程类似于“快速选择”算法我们不是要排序整个数组而只是要找到位于中间位置的那个元素。4.3 代码实现与验证int MoreThanHalfNum_Partition(vectorint nums) { if (nums.empty()) return -1; // 根据题意返回无效值 int n nums.size(); int left 0, right n - 1; int mid n / 2; // 目标位置索引 srand(time(nullptr)); while (true) { int pos Partition_Random(nums, left, right); if (pos mid) { // 找到中位数还需要验证它是否真的超过一半吗 // 根据题目假设一定存在这样的数所以可以直接返回。 // 但严谨的做法可以增加一个验证步骤。 int candidate nums[mid]; // 验证步骤可选但推荐 int count 0; for (int num : nums) { if (num candidate) count; } if (count n / 2) { return candidate; } else { // 理论上不会走到这里除非输入不合法 return -1; } } else if (pos mid) { // 目标在左边 right pos - 1; } else { // 目标在右边 left pos 1; } } }为什么这个方法的时间复杂度是O(n)虽然看起来也有循环和递归但每次Partition操作后我们都会丢弃掉至少一半的区间因为mid是中间位置。数学上可以证明其平均时间复杂度是线性的O(n)。最坏情况每次只排除一个元素下是O(n²)但通过随机化pivot最坏情况概率极低。与摩尔投票法的对比Partition法优点思路直接是“寻找第k大/小元素”问题的通用解法。缺点会修改原数组。平均O(n)但存在不稳定的最坏情况尽管概率低。摩尔投票法优点一次遍历不修改原数组绝对O(n)时间O(1)空间且代码极其简洁。缺点思路比较巧妙需要理解“对拼消耗”的原理。实操心得在面试中如果面试官允许修改原数组你可以提出Partition解法并阐述其与中位数的关系这能展示你对算法本质的理解。但通常摩尔投票法才是这个问题的最优和标准答案因为它无副作用且稳定。你应该同时掌握两种方法并理解摩尔投票法的原理。5. Partition的进阶应用寻找最小的K个数5.1 问题定义与多种解法问题输入整数数组arr和整数k找出数组中最小的k个数。例如arr [4,5,1,6,2,7,3,8], k 4则最小的4个数是[1,2,3,4]不要求顺序。常见解法排序法直接排序后取前k个。时间O(n log n)简单但可能不是最优。堆优先队列法维护一个大小为k的大顶堆。遍历数组若堆未满则入堆若堆已满且当前数比堆顶小则弹出堆顶当前最大的数并压入当前数。遍历完成后堆中的k个数就是最小的k个。时间O(n log k)空间O(k)。适合海量数据n很大且k相对较小的场景因为不需要一次性加载全部数据。基于Partition的快速选择法平均时间O(n)最坏O(n²)空间O(1)。会修改原数组。5.2 快速选择算法详解“寻找最小的k个数”本质上就是“寻找第k小的数”如果找到了第k小的数x那么所有小于x的数就是最小的k-1个数再加上x本身。这正是Partition函数大显身手的地方。算法步骤对数组进行随机Partition操作得到基准值位置pos。比较pos与k-1因为索引从0开始第k小的数索引是k-1。如果pos k-1那么arr[0]到arr[pos]这pos1个数即k个数就是最小的k个数不一定有序。我们可以直接返回前k个元素。如果pos k-1说明第k小的数在左半部分递归地在[left, pos-1]中寻找。如果pos k-1说明第k小的数在右半部分递归地在[pos1, right]中寻找。递归或迭代进行直到找到pos k-1。vectorint GetLeastNumbers_Partition(vectorint arr, int k) { if (k 0 || arr.empty()) return {}; if (k arr.size()) return arr; // 如果k大于等于数组大小直接返回原数组 int left 0, right arr.size() - 1; int target_index k - 1; // 我们要找的最终位置 srand(time(nullptr)); while (left right) { int pos Partition_Random(arr, left, right); if (pos target_index) { // 找到了arr[0..pos]就是最小的k个数 break; } else if (pos target_index) { // 目标在左边 right pos - 1; } else { // 目标在右边 left pos 1; } } // 循环结束后arr[0] 到 arr[target_index] 就是结果 return vectorint(arr.begin(), arr.begin() k); }5.3 与堆解法的深度对比与选型特性基于Partition的快速选择基于大顶堆的解法时间复杂度平均O(n)最坏O(n²)O(n log k)稳定空间复杂度O(1)递归栈深度平均O(log n)O(k)是否修改原数组是否适用场景允许修改输入且对平均性能要求高k的大小适中或较大。海量数据n极大k相对较小不能修改原数据。数据流场景。结果顺序不保证顺序只保证是前k小的数。不保证顺序。稳定性依赖随机化存在不稳定的最坏情况风险。稳定性能可预测。为什么堆解法适合海量数据因为堆解法只需要维护一个大小为k的容器。我们可以逐个读取数据例如从磁盘或网络流而不需要将全部n个数据同时加载到内存中。这是其最大的优势。快速选择法的边界情况处理k 0或k n需要返回空数组或整个数组。当pos target_index时循环结束。此时arr[target_index]是第k小的数它左边的数都小于等于它但左边的数并未排序。这正是题目要求的返回最小的k个数顺序不限。如果要求返回的k个数是有序的则需要在找到后对前k个数进行排序代价是O(k log k)。实操心得面试中这题通常期望你给出多种解法并分析其优劣。你可以这样说 “对于这个问题我有三种思路。第一种是直接排序简单但时间复杂度高。第二种是使用大顶堆特别适合处理数据流或者n非常大而k较小的场景。第三种是利用快排的Partition思想进行快速选择平均时间复杂度是线性的但会修改原数组。在实际工程中如果数据可以全部加载到内存且允许修改快速选择法很高效如果是实时数据流堆方法是更合适的选择。”6. 常见问题、陷阱与排查技巧在实际编码和面试中围绕Partition和快排的问题层出不穷。下面我总结了一些最容易出错的地方和排查技巧。6.1 Partition函数本身的陷阱死循环这通常发生在Hoare分区法或递归区间划分错误时。症状程序运行超时或栈溢出。排查检查递归/循环终止条件在快排递归函数中必须是if (left right) return;。如果是if (left right) return;当区间只有一个元素时left right还会继续分区可能造成无限递归。检查递归区间确认递归调用的是[left, pos-1]和[pos1, right]而不是[left, pos]和[pos, right]。后者会导致pos这个元素被反复处理。检查Hoare分区法的指针移动内层do-while循环必须要有防止越界的检查或者确保pivot值在数组中。对于已排序数组性能极差症状排序一个已排序的大数组时速度非常慢。原因固定选择第一个或最后一个元素作为pivot。解决务必使用随机化pivot选择或“三数取中”法。处理大量重复元素效率低症状数组元素全部或大部分相同排序很慢。原因Lomuto分区法会导致极度不平衡的划分。解决使用Hoare分区法或者更高级的三路划分算法将数组分为“小于、等于、大于”三部分。6.2 在解决“最小k个数”和“超过一半数字”时的特殊问题“最小k个数”中k等于0或大于数组长度n陷阱直接进行Partition会导致索引错误。处理必须在函数开头进行防御性检查。if (k 0) return vectorint(); if (k arr.size()) return arr; // 或者返回arr的拷贝“超过一半数字”中输入不满足题目假设陷阱题目说“一定存在”但实际代码应保持健壮性。处理即使使用Partition法找到了“中位数”最后也应该验证这个数字出现的次数是否真的超过一半。这是一个很好的编程习惯。int candidate nums[mid]; if (count(nums.begin(), nums.end(), candidate) nums.size() / 2) { return candidate; } return -1; // 或者抛出异常修改了原数组陷阱Partition操作会打乱原数组的顺序。这在某些场景下是不可接受的。处理如果要求不能修改原数组则必须选择其他方法如哈希表、摩尔投票法或堆。在面试中一定要先问清楚“是否可以修改输入数组”6.3 调试与测试技巧单元测试用例设计空数组、单元素数组。已排序数组、逆序数组。测试pivot选择策略所有元素都相同的数组。测试重复元素处理随机生成的大规模数组。测试性能对于“最小k个数”额外测试k1,kn,k0,kn的情况。可视化调试对于理解Partition过程可以在代码中打印每次划分前后的数组状态观察pivot如何就位。使用STL进行对照在验证自己实现的“最小k个数”时可以用std::nth_element来对照结果。nth_element就是STL中基于快速选择的实现。vectorint arr_copy arr; nth_element(arr_copy.begin(), arr_copy.begin() k - 1, arr_copy.end()); // arr_copy[0..k-1] 就是最小的k个数7. 从理论到实践工程中的考量与扩展学完了原理和实现我们聊聊在真正的工程项目中该如何应用和选择。7.1 何时选择自己实现何时使用库函数自己实现学习与面试深刻理解算法原理是根本。特殊需求需要特定的分区逻辑、定制化的pivot选择策略或非标准的比较规则。嵌入式或受限环境无法使用完整的标准库。使用库函数强烈推荐在工程中使用排序直接使用std::sort。它是高度优化的混合排序算法通常是IntroSort结合了快排、堆排和插入排序效率、稳定性和安全性都远胜于自己写的教科书式快排。找第k大/小元素使用std::nth_element。它就是基于快速选择的优化实现。找最小的k个数不排序使用std::partial_sort或std::nth_element结合std::copy。原因标准库的实现经过了千锤百炼考虑了各种极端情况如栈溢出保护、不同的数据分布并且针对不同编译器、不同硬件做了优化其可靠性和性能是个人代码难以比拟的。7.2 扩展到其他类似问题Partition思想是解决“选择”和“顺序统计”类问题的利器。掌握了它你可以轻松解决一系列变种问题数组中的第K个最大元素LeetCode 215。这正是“快速选择”算法的直接应用将找“第k小”改为找“第(n-k1)小”即可。把数组排成最小的数剑指Offer 45。这需要自定义比较规则将数字转换成字符串后比较ab和ba但排序的核心依然可以基于Partition思想。颜色分类荷兰国旗问题LeetCode 75。这是三路划分的经典应用题要求将只有0,1,2的数组原地排序。你可以用三个指针p0,p1,p2一次遍历完成这正是Partition思想的升华。调整数组顺序使奇数位于偶数前面剑指Offer 21。这是一个自定义分区条件判断奇偶性的Partition问题。7.3 性能优化的最后思考对于排序现代库的std::sort是终极答案。对于选择问题std::nth_element是首选。那么在必须自己实现的情况下如何写出工业级的快速选择代码防御性编程检查输入有效性空指针、k值范围等。随机化永远使用随机pivot。小数组优化当区间长度小于某个阈值如16时切换到插入排序。迭代代替递归使用栈来模拟递归或者使用尾递归优化避免深度递归可能导致的栈溢出。内存访问优化对于非常大的数据考虑缓存友好性。但这属于非常极致的优化通常不需要。回过头看从Partition这一个基础函数我们能衍生出快速排序又能解决“超过一半的数字”和“最小的k个数”这两个经典问题甚至能触碰到“快速选择”和“顺序统计”这个更大的算法主题。这正体现了数据结构与算法学习的魅力掌握一个核心思想就能以点带面解决一大片问题。我个人的习惯是在理解原理和手写实现之后在工程项目中会毫不犹豫地选择标准库。但这份理解和实现能力是你在遇到那些库函数无法直接解决的、更复杂、更定制化的问题时最坚实的底气。下次面试再被问到这些问题希望你能从容地画出Partition的图示讲清时间复杂度的推导并对比不同解法的适用场景这远比只背出一个答案要精彩得多。