实现 3 路分区以进行快速排序

Question

我正在尝试实施 3 向分区以进行快速排序。我测试了很多自定义测试用例，但如果工作正常，但在某些未知情况下会失败。我不知道我要去哪里。

这是代码。分区：

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 than 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

实现 3 路分区以进行快速排序

Implementing 3 way partitioning for quick sort

c++

sorting

quicksort

dutch-national-flag-problem