c - 快速排序算法实现

Question

我已经在寻找有关快速排序算法的信息。但我仍然无法在 C 上实现它。我正在尝试，但 Quicksort 函数根本不起作用。我在我的代码中找不到错误。请帮助我了解发生了什么。

#include <stdio.h>
#include <stdlib.h>

void swap(int a, int b)
{
    int temp = 0;
    temp = a;
    a = b;
    b = temp;
}

int Partition(int p , int r, int A[r - p + 1])
{
    int j = 0;
    int x = A[r - 1];
    int i = p - 1;
    for(j = p - 1; j < r - 1; j++) {
        if(A[j] <= x) {
            i = i + 1;
            swap(A[i], A[j]);
        }
    }
    swap(A[i], A[r - 1]);
    return i + 1;
}

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

int main(int argc, char *argv[])
{
    int A[] = {10, 5, 1, 3, 9, 2, 4, 8, 7, 6};
    int i = 0;
    int length = sizeof(A) / sizeof(int);
    Quicksort(1, length , A);

    for(i = 0; i < length; i ++) {
    printf("%d ", A[i]);
    }
    printf("\n");
return 0;
}

Answer 1

您必须将值作为指向 swap 函数的指针传递

void swap(int *a, int *b)
{
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}

然后改变

swap(A[i], A[j]);

到

swap(&A[i], &A[j]);

和

swap(A[i], A[r - 1]);

到

swap(&A[i], &A[r - 1]);