数据透视表重复时的 C++ 分区整数

Question

更新:

我本来是想找一个划分数组的划分算法，作为快速排序算法的一部分。

比如像这样的数组:

[5, 3, 2, 4, 3, 1]

基于3的枢轴，到

[smaller than 3 || 3, 3, larger than 3]

最后发现其实不用上面的partition，下面的结果也可以让quick sort工作:

[smaller than 3 || 3, larger or equal than 3]

这意味着 3 个不需要彼此相邻。

我的代码如下(

int partition(std::vector<int>& v, int pivot)
{
  int left = 0;
  int right = v.size()-1;
  while (left != right)
  {
    while (v[left] < pivot) ++left;
    while (pivot < v[right]) --right;
    swap(v[left], v[right]);
  }
  return left;
}

Ben 注意到我应该用相等更新一个条件，这样一个条件是“<”，另一个是“>=”，这将使条件完整。

但是，分区

5, 3, 2, 4, 3, 1

基于枢轴 3，将是

< 3 || 3, 4, 3, 5

And 和 threes 不相邻。

真正的好东西出来了，三元组是否相邻其实并不重要。因为经过仔细思考快速排序算法，这个分区最终会让数组排序。

Answer 1

将您的其中一个运算符(operator)更改为 <= , 而不是 < .

while (v[left] < pivot) ++left;
while (pivot <= v[right]) --right;

这样，每个数字都符合两个标准之一。要么它小于主元，它向左移动，要么它小于或等于它，它向右移动。没有中间立场。

对于广义比较仿函数，您可以简单地交换参数并反转结果以获得相同的效果:

while ( compare(v[left], pivot) ) ++left;
while ( !compare(v[right], pivot) ) --right;