0

我正在尝试实现 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);
}

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

4

1 回答 1

2

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

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);

演示

于 2020-05-18T13:11:36.433 回答