c++ - 随机快速排序的分区(具有很少的独特元素)

Question

我的任务是为具有少量元素的随机快速排序编写一个分区函数(通过包含 3 个分区而不是 2 个分区对其进行优化)。我试过实现我的版本，发现它没有通过测试用例。

但是，通过使用同学版本的分区，它似乎可以工作。从概念上讲，我看不出他和我之间的区别，而且我不知道是什么导致我的版本崩溃。我用他(我认为)的概念编写它，其中涉及使用计数器(j 和 k)将数组划分为 3。

我将不胜感激任何可以指出为什么我的不起作用的人，以及我应该做些什么来尽量减少再次发生这种情况的机会。我觉得这个学习点对我作为开发人员很重要，谢谢!

为了比较，将有 3 block 代码，下面的代码片段将是我的分区版本，接下来是我同学的版本，最后是运行我们分区的实际算法。

我的版本(不起作用)

vector<int> partition2(vector<int> &a, int l, int r) {
  int x = a[l];
  int j = l;
  int k = r;

  vector<int> m(2);

  // I've tried changing i = l + 1
  for (int i = l; i <= r; i++) {
    if (a[i] < x) {
      swap(a[i], a[j]);
      j++;
    }

    else if (a[i] > x) {
      swap(a[i], a[k]);
      k--;
    }
  }

  // I've tried removing this
  swap(a[l], a[j]);

  m[0] = j - 1;
  m[1] = k + 1;

  return m;
}

我的同学(有效)

vector<int> partition2(vector<int> &a, int l, int r) {
    int x = a[l];
    int p_l = l;
    int i = l;
    int p_e = r;
    vector<int> m(2);
    while (i <= p_e) {
        if (a[i] < x) {
            swap(a[p_l], a[i]);
            p_l++;
            i++;
        } else if (a[i] == x) {
            i++;
        } else {
            swap(a[i], a[p_e]);
            p_e -= 1;
        }
        m[0] = p_l - 1;
        m[1] = p_e + 1;
    }
    return m;
}

实际的快速排序算法

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

  int k = l + rand() % (r - l + 1);
  swap(a[l], a[k]);
  vector<int> m = partition2(a, l, r);

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

Answer 1

三路分区的两个函数的区别在于你的代码前进了i在每次循环中，但你同学的函数前进i仅当位置 i 处的值小于或等于枢轴。

让我们看一个示例数组。第一个值 3 是枢轴。字母表示每次通过循环后变量的位置。

j               k
3   1   5   2   4
    i

下一个值更小:将其交换到左侧并前进 j :

    j           k
1   3   5   2   4
        i

下一个值 5 更大，所以它向右:

    j       k
1   3   4   2   5
            i

这是一个糟糕的举动:你的 i现在已经跳过了 4，它也必须转到正确的部分。你同学的密码没有提前 i在这里并在下一次传球中接住 4。

您的循环有一些不变量，所有通过后必须为真的事情:

索引低于 i 的所有项目小于枢轴。

索引大于 k 的所有项目大于枢轴。

索引来自 j 的所有项目至i - 1等于枢轴。

所有项目来自 i至k尚未处理。

您还可以从中确定循环条件:

根据定义，枢轴是最左边的元素，因为快速排序函数将其交换到那里。它必须属于等于枢轴的元素组，因此您可以从 l + 1 开始循环.

从 k 开始的所有项目已经在数组的正确部分。这意味着您可以在 i 时停止。达到k .更进一步将不必要地在“大于”分区内交换元素并移动 k ，这将返回错误的分区边界。