为快速排序实现3种方式的分区

Question

我正在尝试实现3-Way分区以进行快速排序。我测试了许多自定义测试用例，但工作正常，但对于某些未知用例却失败了。我不知道要去哪里。

这是代码。分区：

int* partition3(vector<long long int> &a, int l, int r) {
  int* m = new int[2];

  long long int x = a[l];

  int j = l;
  int k = l;

  for (int i = l + 1; i <= r; i++) {

    if (a[i] < x) {
      j++;
      k++;
      swap(a[i], a[j]);
    }
    else if(a[i]==x)
    { 
      k++;
      swap(a[i],a[k]);
    }
  }
  swap(a[l], a[j]);    
  m[0]=j;
  m[1]=k;
  return m;
}

排序功能：

void randomized_quick_sort(vector<long long int> &a, int l, int r) {
  if (l >= r) {
    return;
  }

  int k = l + rand() % (r - l + 1);

  swap(a[l], a[k]);

  int* m = new int[2];

  m = partition3(a, l, r);

  randomized_quick_sort(a, l, m[0]-1);
  randomized_quick_sort(a, m[1], r);
}

如果您能帮助我，我将不胜感激。

Answer 1

被证明是正确的实现三向分区的最简单方法是使用循环不变式的方法。为了简单和通用起见，让我们使用迭代器。考虑以下不变量：

In the range
  [first, i)  all elements are less then pivot
  [i, j)      all elements are equal to pivot
  [j, k)      unpartitioned range
  [k, last)   all elements are greater than pivot

最初是i = first，j = first和k = last，因此整个范围[first, last)是未分区的。在每次迭代中，我们将这个范围缩小一个元素。最后，j = k，以便整个范围被三分。

以下代码实现了这个想法：

template<class It>
std::pair<It, It> three_way_partition(It first, It last) {
    assert(first != last);    
    const auto& pivot = *--last;

    auto i = first, j = first, k = last;
    while (j != k)
        if (*j < pivot)
            std::iter_swap(i++, j++);
        else if (pivot < *j)
            std::iter_swap(j, --k);
        else
            ++j;

    std::iter_swap(j++, last);
    return {i, j};
}

这里我使用最后一个元素作为枢轴。此选择可简化代码，但不是必需的。

使用此功能的快速排序算法是：

template<class It, class Gen>
void randomized_quick_sort(It first, It last, Gen&& gen) {
    if (last - first <= 1)
        return;

    std::uniform_int_distribution<typename It::difference_type> 
        dist(0, last - first - 1);
    std::iter_swap(first + dist(gen), last - 1);

    const auto p = three_way_partition(first, last);
    randomized_quick_sort(first, p.first, gen);
    randomized_quick_sort(p.second, last, gen);
}

示例用例：

std::mt19937 gen; // you might want to initialize it with std::random_device
std::vector<int> vec;
// initialize vec

randomized_quick_sort(vec.begin(), vec.end(), gen);

Demo