如果你学习过算法，那么肯定听说过快速排序的大名，但是对于快速排序中用到的 partition 算法，你了解的够多吗？或许是快速排序太过于光芒四射，使得我们往往会忽视掉同样重要的 partition 算法。

Partition 可不只用在快速排序中，还可以用于Selection algorithm（在无序数组中寻找第K大的值）中。

Partition实现

用 Two Pointers 的思想，保持头尾两个指针向中间扫描，每次在头部找到大于pivot的值，同时在尾部找到小于pivot的值，然后将它们做一个交换，就可以一次把这两个数字放到最终的位置。一种比较明智的写法如下：

int partition(vector<int> & arr, int low, int high){
  int pivot = arr[low];
  while(low<high){
    //比较时如果少了等于号,就有可能会陷入死循环,两个重复的数不断交换
    while(low<high && arr[low]<=pivot) low++;
    arr[high] = arr[low];
    while(low<high && arr[high]>=pivot) high--;
    arr[low] = arr[high];
  }
  arr[low] = pivot;
  return low;
}

上面的算法虽然没有显式用的swap,但实际上也相当于进行了swap操作,如下图所示:

Partition应用

快排


void quick_sort(vector<int> & arr, int low, int high){
  if(low >= high) return;
  mid = partition(arr,low,high);
  if(mid>low) quick_sort(arr, low,mid-1);
  if(mid<high) quick_sort(arr,mid+1, high);
}

复杂度:$O(nlogn)$

寻找无序数组中第K大的值

首先用 partition 将数组分为两部分，得到分界点下标 pos，然后分三种情况：

pos == k-1，则找到第 K 大的值，arr[pos]；
pos > k-1，则第 K 大的值在左边部分的数组。
pos < k-1，则第 K 大的值在右边部分的数组。

int find_kth_number(int k){
  int low = 0; int high = arr.size()-1;
  while(low< high){
    pos = partition(arr,low,high);
    if(pos==k-1)
      return arr[k-1];
    else if (pos < k-1)
      low = pos+1;
    else
      high = pos-1;
  }
}

时间复杂度 $O(n)$

分析:
考虑最坏情况下，每次 partition 将数组分为长度为 N-1 和 1 的两部分，然后在长的一边继续寻找第 K 大，此时时间复杂度为 O(N^2 )。不过如果在开始之前将数组进行随机打乱，那么可以尽量避免最坏情况的出现。而在最好情况下，每次将数组均分为长度相同的两半，运行时间 T(N) = N + T(N/2)，时间复杂度是 O(N)。

Partition 进阶

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

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