0

我使用 Cormen Algorithms 书中的 Hoare 分区对 Quicksort 进行编码。我无法在我的代码中发现任何错误，它看起来就像书中的伪代码。

swapping i, j : 0, 8
-2 2 -5 -3 6 0 1 0 -1 4

swapping i, j : 1, 3
-2 -3 -5 2 6 0 1 0 -1 4
p is: 2

swapping i, j : 0, 1
-3 -2 -5 2 6 0 1 0 -1 4
p is: 0

完成上述交换后，此代码最终会在 subarray 上进行分区{-3, -2}。为此subarray，pivot is-3和 the partition() returns 0as the index (j)。由于该子数组已经-3在0th index位置处使用枢轴进行排序，因此每次快速排序时都不会进行任何更改。所以 qsort 永远循环。

有人可以告诉我这与书中的 Hoare 分区有何不同，如果相同，为什么这不起作用？

void swap(int *a, int i, int j) {
        cout << "swapping i, j : " << i << ", " << j << endl;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp; }

int partition(int *a, int len) {
        int pivot = a[0];

        int i = -1, j = len;
        while (true) {
               while ( ++i && a[i] < pivot && i< j) {}
               while (--j && a[j] > pivot && i <j) {}
               if (i < j )
                  swap(a, i, j);
               else 
                  return j ;
        } }

void qsort(int a[], int len) {
        int p = partition(a, len);
        cout << "p is: " << p << endl;
        qsort(a, p);
        qsort(a+p, len - p ); }

int main(int argc, char *argv[]) {
        int a[10] = {-1, 2, -5, -3, 6, 0, 1, 0, -2, 4};
        qsort(a, 10); }
4

1 回答 1

1

在答案中扩展我的评论，partition()返回0-based index，但您需要将数组长度（长度为1-based）传递给qsort()，所以它必须是：

void qsort(int a[], int len)
{
    int p = partition(a, len);
    cout << "p is: " << p << endl;
    qsort(a, p + 1); // note p+1 instead of p
    qsort(a + p + 1, len - (p + 1)); // note p+1 instead of p
}

试运行将如下所示：

swapping i, j : 0, 8
-2 2 -5 -3 6 0 1 0 -1 4

swapping i, j : 1, 3
-2 -3 -5 2 6 0 1 0 -1 4
p is: 2

现在您必须调用qsort(a, 3)，因为您想对子数组进行排序-2 -3 -5。此外， qsort(a+3, 7) 用于子数组2 6 0 1 0 -1 4

于 2017-04-26T05:41:08.203 回答