4

我发现这种快速排序分区方法令人困惑和错误，但它似乎有效。我指的是这个伪代码。注意：他们在文章末尾也有一个 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;
}

并产生这个输出：

1 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 数组。

我还尝试将此分区函数用于选择算法，但未能产生正确的结果。它似乎可以工作，但是作为快速排序算法的一部分，它甚至非常快。

所以我的问题是：

  1. 任何人都可以发布一个算法不起作用的例子吗？
  2. 如果没有，为什么它会起作用，因为分区部分似乎是错误的？这是我不知道的另一种分区方法吗？
4

4 回答 4

4

我认为分区是正确的。7是支点。原始数组被划分为一个长度为 5 的子数组，其中包含小于或等于 7 的元素，以及一个长度为 2 的子数组，其中包含大于或等于 7 的元素。

于 2010-05-21T13:58:02.010 回答
1

从这里往上延伸应该是这个样子

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; 
}
于 2011-03-09T04:45:09.713 回答
0

来自维基百科（我强调了我认为直接解决您问题的部分）：

这是就地分区算法。它通过将所有小于或等于 array[pivotIndex] 的元素移动到子数组的开头，将所有更大的元素留在它们后面，从而将数组的部分在索引之间划分为左和右，包括在内。在此过程中，它还会找到它返回的枢轴元素的最终位置。它暂时将枢轴元素移动到子数组的末尾，以免妨碍它。因为它只使用交换器，所以最终列表具有与原始列表相同的元素。请注意，一个元素在到达其最终位置之前可能会被多次交换。还应该注意的是，在输入数组中存在重复数据的情况下，它们可以分布在左子数组中，可能以随机顺序。这并不代表分区失败，因为进一步的排序将重新定位并最终将它们“粘合”在一起。

这可能是你所缺少的吗？

于 2010-05-21T14:25:52.107 回答
0

您在项目的索引和 item 值之间感到困惑

看看你的标题

int partition(int a[], int p, int r) ;

现在，如果我们将数组 a 上的数据类型更改为一些奇怪的数据类型，您将看到问题

int partition( Otherdatatype a[], int p, int r) ;

您从 main 中调用该函数

partition(a, 1, a[0]);

请参阅问题 a[0] 是 a[0] 中条目的值而不是索引值。

想象一下 a[0] 在您的代码中有值 200 只需将第一项值更改为 200 并且您将收到运行时错误“尝试访问超出范围的内存”，因为如果您遵循通过 a[0] = 200作为值 r 进入分区，然后遵循分区内部发生的情况。

要记住的是，这是分区标头中的排序例程，数组 a 中的列表可能与索引的类型不同.. 标头的 p 和 r 显然是指索引位置的索引，而 a 是列表要排序。

因此，您的主要开始是

partition(a, 0, items_in_array-1);

你明白为什么吗？数组 a 从 a[0] ... a[items_in_array-1] 运行

因此，在上面的示例中，您已将 8 个值预加载到数组中，因此您从 main 调用的分区应该是

partition(a, 0, 7);
于 2011-03-09T04:10:55.893 回答