three way partition

问题描述

partition算法就是将我们的一个数组中的数分成高低两部分，返回分割点的位置。
而三路划分将数组中的数分成三个部分，大于/小于/等于某个值，分割点有两个。这样处理往往能提升我们的效率（可以尽快地减少我们需要寻找的范围）

three way partition是一种划分思想，我们需要的通常是那两个划分点，具体怎么使用这两个划分点请依照你的实际需要。

直接看代码

两种风格，一是从一头扫描，另一种从两头扫描，两头扫描更优。

int three_way_partition(vector<int> &L, int l, int r, int target) {
  // after partition, it's like:
  // ---[=]=[=]+++
  //    low high
  int i = l, low = l, high = r;
  while (i <= high) {
    if (L[i] == target)
      ++i;
    else if (L[i] < target)
      swap(L[i++], L[low++]);
    else
      swap(L[i], L[high--]);
  }
  // do something with low, high...
}

示例代码

可以参考median of medians中使用的three way partition。

BFPRT.cpp中的三路划分是从一头扫描。（直接从wiki源代码翻译过来），BFPRT-simple.cpp中的使用的是两头扫描版本。

参考

• wiki: Dutch national flag problem
• csdn: 三分法 three-way partitioning