C 问题中的快速排序

Question

我在用 C 编写的快速排序程序中卡在了某个点。谁能指出错误在哪里？我的代码没有运行，我已经尝试将它与多个在线程序进行比较。我明天有一个测试，我想在尝试之前知道错误是什么。

#include <stdio.h>

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

int partition(int a[],int l,int h){
    int pi=l,i=l,j=h;
    while(i<j){
            while(a[i]<=a[pi])
                i++;
            while(a[j]>a[pi])
                j--;
            if(i<j){
                swap(a[i],a[j]);
            }
        }
    swap(a[j],a[pi]);
    return j;
}

void quicksort(int a[],int l,int h){
    int j;
    j=partition(a,l,h);
    quicksort(a,l,j-1);
    quicksort(a,j+1,h);
}

int main(){
    int n,i;
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    int a[n];
    printf("Enter the elements: ");
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    quicksort(a,0,n-1);
    printf("The array after sorting is: ");
    for(i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

Answer 1

函数参数在 C 中通过值传递。您的swap函数：

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

获取两个整数参数，int a 和 int b。在函数内，它们的行为类似于局部变量，因此在 swap 函数内对 a 和 b 的更改对调用者 没有影响。

为了模仿引用传递的效果，可以用指针传递要修改值的对象的地址，解引用 函数内部的指针，用于访问要修改的对象。

比如你的swap函数可以修改如下：

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

还需要修改对该函数的调用，以传递要交换值的对象的地址。例如，swap(a[i],a[j]); 需要更改为 swap(&a[i],&a[j]);（或等效地更改为 swap(a+i,a+j);）。

Answer 2

您的代码有几个问题。

首先，你的交换函数交换局部变量a和b，但它不会影响partition中的数组a。 Ian Abbott 对此进行了更详尽的解释。

解决这个问题的一种方法是通过指针传递数组元素的地址，以便 swap 可以访问和更改它们。一种更简单的方法是编写一个对数组索引进行操作的交换函数：

void swap(int array[], int i, int j)
{
    int t = array[i]; array[i] = array[j]; array[j] = t;
}

其次，必须在某个时候停止递归。当你有一个只有一个元素或根本没有元素的数组时，没有什么可做的，因为数组（或子数组）已经排序。

所以在这种情况下不要做任何事情。或者，更确切地说，只有当你至少有两个元素时才做某事。这有一个很好的副作用，即 recusrion 实际上停止了。 :)

void quicksort(int a[], int l, int h)
{
    if (l < h) {
        int j;

        j = partition(a, l, h);
        quicksort(a, l, j - 1);
        quicksort(a, j + 1, h);
    }
}

C 问题中的快速排序

Quick Sort in C Issue

c

quicksort