为什么这种速战速决有效？
我发现这种快速分区方法既混乱又错误，但它似乎有效。我指的是这个伪码。Note：文章末尾还有一个C实现，但它与它们的伪代码有很大不同，所以我不关心这一点。
我还像这样用C编写了它，尽量保持伪代码的真实性，即使这意味着要做一些奇怪的C操作：
#include <stdio.h>
int partition(int a[], int p, int r)
{
int x = a[p];
int i = p - 1;
int j = r + 1;
while (1)
{
do
j = j - 1;
while (!(a[j] <= x));
do
i = i + 1;
while (!(a[i] >= x));
if (i < j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
else
{
for (i = 1; i <= a[0]; ++i)
printf("%d ", a[i]);
printf("- %d\n", j);
return j;
}
}
}
int main()
{
int a[100] = //{8, 6,10,13,15,8,3,2,12};
{7, 7, 6, 2, 3, 8, 4, 1};
partition(a, 1, a[0]);
return 0;
}如果您运行这个程序，您将得到以下输出：
1 6 2 3 4 8 7-5
但是，这是错误的，不是吗？显然，a[5]并不是所有的值都比它低，因为a[2] = 6 > a[5] = 4。更不用说，7应该是支点(初始a[p])，但它的位置既不正确，也不正确。
下面的分区算法取自维基百科
int partition2(int a[], int p, int r)
{
int x = a[r];
int store = p;
for (int i = p; i < r; ++i)
{
if (a[i] <= x)
{
int t = a[i];
a[i] = a[store];
a[store] = t;
++store;
}
}
int t = a[r];
a[r] = a[store];
a[store] = t;
for (int i = 1; i <= a[0]; ++i)
printf("%d ", a[i]);
printf("- %d\n", store);
return store;
}并产生这样的输出：
6 2 3 8 4 7-1
在我看来，这是一个正确的结果:枢轴(a[r] = a[7])已经达到了它的最终位置。
但是，如果在以下算法中使用初始分区函数：
void Quicksort(int a[], int p, int r)
{
if (p < r)
{
int q = partition(a, p, r); // initial partitioning function
Quicksort(a, p, q);
Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r.
}
}..。这似乎是一种正确的排序算法。我在许多随机输入上测试了它，包括长度为20的所有0-1数组。
我还尝试使用这个分区函数作为选择算法，其中它未能产生正确的结果。但是，作为快速排序算法的一部分，它似乎工作得很好，甚至非常快。
所以我的问题是：
- 有人能发布一个算法不起作用的例子吗？
- 如果没有，为什么要工作，因为分区部分似乎是错误的。这是另一种我不知道的分区方法吗？
回答 4
Stack Overflow用户
发布于 2010-05-21 13:58:02
我认为分区是正确的。7是支点。将原始数组划分为长度5的子数组，该子数组包含小于或等于7的元素，以及长度2的子数组，该子数组包含大于或等于7的元素。
Stack Overflow用户
发布于 2011-03-09 04:45:09
从上面延伸到这里应该是什么样子
void swap(int *a, int *b)
{
int x;
x = *a;
*a = *b;
*b = x;
}
int partition(int s[], int l, int h)
{
int i;
int p;/* pivot element index */
int firsthigh;/* divider position for pivot element */
p = h;
firsthigh = l;
for (i = l; i < h; i++)
if(s[i] < s[p]) {
swap(&s[i], &s[firsthigh]);
firsthigh++;
}
swap(&s[p], &s[firsthigh]);
return(firsthigh);
}
void quicksort(int s[], int l, int h)
{
int p;/* index of partition */
if ((h - l) > 0) {
p = partition(s, l, h);
quicksort(s, l, p - 1);
quicksort(s, p + 1, h);
}
}
int main()
{
int a[100] = //{8, 6,10,13,15,8,3,2,12};
{7, 7, 6, 2, 3, 8, 4, 1};
quicksort(a, 0, 7);
return 0;
} Stack Overflow用户
发布于 2010-05-21 14:25:52
来自维基百科 (我强调了我认为直接回答你问题的部分)：
这是就地分区算法。它通过将小于或等于arraypivotIndex的所有元素移动到子数组的开头，从而将数组中的部分从左到右进行划分，并将所有更大的元素保留在它们后面。在此过程中，它还会找到它返回的pivot元素的最终位置。临时将枢轴元素移动到子数组的末尾，这样它就不会碍事。，因为它只使用交换，所以最终列表具有与原始列表相同的元素。注意，在到达元素的最后位置之前，可以多次交换元素。还应该注意的是，在输入数组中出现枢轴重复的情况下，它们可以分布在左子数组上，可能是随机顺序的。这并不代表分区失败，因为进一步的排序将重新定位并最终将它们“粘合”在一起。
那会是你错过的吗？
https://stackoverflow.com/questions/2882391
复制相似问题
腾讯云开发者
