时间戳

首页 > 解决方案 > C问题中的快速排序

c - C问题中的快速排序

问题描述

我在 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;
}

标签： cquicksort

解决方案

您的代码有几个问题。

首先，您的交换函数交换局部变量a和b，但不会影响a. partitionIan Abbott 对此进行了更彻底的解释。

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

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

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

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

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);
    }
}

推荐阅读