partition算法是一种分类算法，简单来说就把一个序列分成前后两部分，前一部分都是满足某一条件的元素，后一部分都是不满足该条件的元素。关于partition算法最著名的应用就是quick sort（快速排序）了

除了快速排序外，partition算法还经常用在下列场合：

在O(N)的时间内找出一个序列中第k大（小）的元素。在O(N)的时间内找出一个序列中所有比k大（小）的元素。

快速排序的partition算法

简单来说就是通过partition算法将待排序序列划分为以pivot（中间）值为分界点的两个子序列，一个子序列所有元素的值都小于pivot，另一个子序列所有元素的值都大于等于pivot，然后再对每个子序列递归进行这样的操作。

int partition2(vector<int> &arrs, int begin, int end) { int pivot = arrs[begin]; while (begin < end) { while (begin < end && arrs[--end] >= pivot); arrs[begin] = arrs[end]; while (begin < end && arrs[++begin] <= pivot); arrs[end] = arrs[begin]; } arrs[begin] = pivot; return begin; }

注意：begin是第一个元素的下标，end是arr最后一个元素的下一个元素下标。

第二种方法：

int partition3(vector<int>&arr, int begin, int end) { int pivot = arr[begin]; int pos = begin; for (int i = begin + 1; i < end;i++) { if (arr[i] < pivot) swap(arr[++pos], arr[i]); } swap(arr[begin], arr[pos]); return pos; }

 区别：第一种方法有两个指针，可以从两边向中间处理，数据移动次数较少，第一种方法只有一个指针，如果从小到大排序，前面有一个数大于pivot基准，需要多次比较移动后才能到达后面。

Partition 应用

我们都知道经典的快速排序就是首先用 partition 将数组分为两部分，然后分别对左右两部分递归进行快速排序，过程如下

void quick_sort(vector<int>&arr, int begin, int end) { if(begin>=end-1)//end是最后一个元素下一个元素下标 return; int pos=partition(arr,begin,end); quick_sort(arr,begin,pos); quick_sort(arr,pos+1,end); }

虽然快排用到了经典的分而治之的思想，但是快排实现的前提还是在于 partition 函数。正是有了 partition 的存在，才使得可以将整个大问题进行划分，进而分别进行处理。

除了用来进行快速排序，partition 还可以用 O(N) 的平均时间复杂度从无序数组中寻找第K大的值。和快排一样，这里也用到了分而治之的思想。首先用 partition 将数组分为两部分，得到分界点下标 pos，然后分三种情况：

pos == k-1，则找到第 K 大的值，arr[pos]；pos > k-1，则第 K 大的值在左边部分的数组。pos < k-1，则第 K 大的值在右边部分的数组。 int find_kth_number(vector<int>& arr,int k) { int begin=0; int end=arr.size(); if(k<0||k>end) return 0; int target; while(begin<end) { int pos=partition(arr,begin,end); if(pos=k-1) { target=arr[pos]; break; } else if(pos>k-1) end=pos-1; else begin=pos+1; } return target; }

Partition 进阶

接下来先考虑这样一个问题，给定红、白、蓝三种颜色的小球若干个，将其排成一列，使相同颜色的小球相邻，三种颜色先后顺序为红，白，蓝。这就是经典的 Dutch national flag problem。

我们可以针对红，蓝，白三种颜色的球分别计数，然后根据计数结果来重新放球。不过如果我们将问题进一步抽象，也就是说将一个数组按照某个target值分为三部分，使得左边部分的值小于 target，中间部分等于 target，右边部分大于 target，这样就不能再用简单的计数来确定排序后的结果。这时候，就可以用到另一种 partition 算法：three-way-partition。它的思路稍微复杂一点，用三个指针将数组分为四个部分，通过一次扫描最终将数组分为 <，=，> 的三部分，如下图所示：

                                                                                            三分划分

// Assume target is in the arr. void three_way_partition(vector<int>& arr,int target) { int next_less_pos=0,next_bigger_pos=arr.size()-1,next_scan_pos=0; while(next_scan_pos<=next_bigger_pos) { if(arr[next_scan_pos]<target) { swap(arr[next_scan_pos++],arr[next_less_pos++]); } else if(arr[next_scan_pos]>target) swap(arr[next_scan_pos],arr[next_bigger_pos--]); else next_scan_pos++; } } }

这里的主要思想就是在一遍扫描中，通过交换不同位置的数字，使得数组最终可以维持一定的顺序，和前面快排中用到的 partition 思想一致。区别在于快排按照 pivot 将数组分为两部分，左右部分中的值都可能等于 pivot，而 three-way-partition 将数组分为 <, =, >的三部分。

文章部分内容来源： https://selfboot.cn/2016/09/01/lost_partition/