随机快速排序的分区（具有很少的唯一元素）

Question

我的任务是为具有少量元素的随机快速排序编写分区函数（通过包含 3 个分区而不是 2 个分区来优化它）。我已经尝试实现我的版本，但发现它没有通过测试用例。

不过，用同学版的分区，好像还行。从概念上讲，我看不出他的和我的有什么区别，我也不知道是什么导致我的版本崩溃。我是用他的概念写的（我想），这涉及到使用计数器（j和k）将数组划分为3.

如果有人能指出我的为什么不起作用，以及我应该如何做才能将再次出现这种情况的可能性降到最低，我将不胜感激。我觉得这个学习点对我作为开发者来说很重要，谢谢！

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

我的版本（不工作）

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 =13=] 小于或等于主元。

让我们来看一个示例数组。第一个值 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 时停止。进一步将不必要地交换 "greater than" 分区内的元素并移动 k，这将 return 错误的分区边界。

随机快速排序的分区（具有很少的唯一元素）

Partition for randomised quicksort (with few unique elements)

c++

sorting

algorithm

quicksort