我的任务是为一个只有几个元素的随机快速排序编写一个分区函数(通过包括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);
}
三元分区的两个函数之间的区别在于，您的代码在每次循环中都会前进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的所有项目尚未处理
您还可以根据以下内容确定环路条件：
- 根据定义，pivot是最左边的元素，因为quicksort函数在那里交换它。它必须属于与枢轴相等的元素组，因此可以在
l + 1开始循环 - 从
k开始的所有项目都已在数组的正确部分中。这意味着您可以在i达到k时停止。更进一步将不必要地交换"大于"分区内部的元素，并移动k，这将返回错误的分区边界