Quicksort程序未对数组进行排序

Quicksort程序未对数组进行排序

我还不知道代码有什么问题:

#include <stdio.h>
#define cutoff 3
int swap(int *x, int *y)
{
    int *tmp;
    tmp = x;
    x = y;
    y = tmp;
    return *x, *y;
}
void qsort(int a[], int left, int right)
{
    int i, j;
    int pivot;
    if (left + cutoff <= right) // JUST TO ENSURE THAT THE ARRAY'S SIZE IS >= CUTOFF.
    {
        pivot = median(a, left, right);
        i = left;
        j = right - 1;
        for (;;)
        {
            while (a[i] < pivot)
                i++;
            while (a[j] > pivot)
                j--;
            if (i < j)
                swap(&a[i], &a[j]);
            else
                break;
        }
        swap(&a[i], &a[right - 1]); // RESTORE PIVOT
        qsort(a, left, i-1);
        qsort(a, i+1, right);
    }
    //else
        // PERFORM INSERTION SORT
}
void quicksort(int a[], int n)
{
    int i;
    qsort(a, 0, n - 1);
    printf("THE SORTED ARRAY IS: ");
    for(i=0;i<n;i++)
        printf("%d ", a[i]);
}
int median(int a[], int left, int right)
{
    int center = (left + right) / 2;
    if(a[left] > a[center])
        swap(&a[left], &a[center]);
    if(a[left] > a[right])
        swap(&a[left], &a[right]);
    if(a[center] > a[right])
        swap(&a[center], &a[right]);
    swap(&a[center], &a[right - 1]); // HIDE PIVOT.
    return a[right - 1]; // RETURN PIVOT.
}
void main()
{
    int a[100], i, n;
    printf("ENTER THE SIZE: ");
    scanf("%d", &n);
    printf("ENTER THE UNSORTED ARRAY: ");
    for (i=0;i<n;i++)
        scanf("%d", &a[i]);
    quicksort(a, n);
}


输出与输入相同,因此有时占用的空间大于输入大小。我认为问题出在median函数,选择枢轴。

最佳答案

int swap(int *x, int *y)
{
    int *tmp;
    tmp = x;
    x = y;
    y = tmp;
    return *x, *y;
}


您是在分配指针,而不是它们的值。改用这个

void swap(int *x, int *y)
{
    int tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}


同样,返回值没有任何意义,因为这些值已被指针交换,并且您一次也不能返回2个值。返回类型应该像@Yu Hao一样无效

关于c - Quicksort程序未对数组进行排序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22282348/

10-09 08:41