-1

为什么我的QuickSort工作不正常？这意味着它不会从数组中整理出值。这是我对一个简单的 5 元素数组的输出：

未排序的数组，就可以了：

A[0] = 8
A[1] = 1
A[2] = 45
A[3] = 78
A[4] = 234

但这是一个排序数组，至少根据我的代码：

A[0] = 8
A[1] = 234
A[2] = 45
A[3] = 78
A[4] = 1

和代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>

void printOutAnArray(int *A, int n)
{
    int i;
    for(i=0; i<n; i++)
    {
        printf("A[%d] = %d\n", i, A[i]);
    }
}

void swap(int *i, int *j)
{
    int t = *i;
    *i = *j;
    *j = t;
}

int partition(int A[], int p, int r)
{
    int x = A[p];
    int i = p;
    int j = r+1;

    while (true)
    {
        do j --; while (A[j] <= x);

        do i ++; while(A[i] >= x);

        if (i < j)
            swap(&A[i], &A[j]);
        else
            return j;
    }
}

void Quicksort(int A[], int p, int r)
{
    if (p < r)
    {
        int q = partition(A,p,r);
        Quicksort(A, p, q-1);
        Quicksort(A, q+1, r);
    }
}

int main(int argc, char **argv)
{

    int A[] = {8, 1, 45, 78, 234};
    int n = 5;

    printOutAnArray(A, n);
    printf("\n");

    Quicksort(A, 0, n-1);

    printOutAnArray(A, n);


    return 0;
}
4

1 回答 1

2

好吧，它没有排序，因为它实现不正确。一些明显的问题partition

  • 分区元素最终必须移动到分区之间的位置。你永远不会那样做。我看到您使用子数组的第一个元素（即A[p]）作为分区元素。它仍然处于第一位。你永远不会将它移动到其他任何地方。

    例如，在第一次调用partition您时，将8其用作分区元素。但是你永远不会8从A[0]位置上重新定位它。典型的实现通常会将该元素交换到其在分区之间的最终位置。

  • 这些小do/while周期中的条件似乎是为降序定制的。你打算做一个降序排序吗？还是您只是混淆了条件？

  • 那些小循环do/while似乎很容易出现数组边界溢出。想想如果你的原始数组包含相同的元素会发生什么。

于 2013-11-04T22:22:24.503 回答