c - C 中的快速排序未按预期工作

Question

我尝试用 C 语言实现 QuickSort，但没有得到正确的结果。这是我写的程序。

#include<stdio.h>
int partition(int a[],int low,int high)
{
    int pivot = a[high];
    int temp;
    int i = low-1;
    int j=0;
    for(j=0;j<high-1;j++)
    {
        if(a[j]<=pivot)
        {
            i=i+1;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;    
        }       
    }
    temp = a[i+1];
    a[i+1] = pivot;
    a[high] = temp;
    return (i+1);   
}

void quick_sort(int a[],int low,int high)
{
    if(low<high)
    {
        int q = partition(a,low,high);
        quick_sort(a,low,q-1);
        quick_sort(a,q+1,high);
    }
}

main()
{
    int i,n,a[10];
    printf("\nEnter the number of elements in the array : ");
    scanf("%d",&n);
    printf("\nEnter the elements in the array : "); 
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("\nElements in the array before sorting : ");    
    for(i=0;i<n;i++)
    {
        printf (" %d",a[i]);
    }
    quick_sort(a,0,n-1);
    printf("\nElements in the array after sorting : "); 
    for(i=0;i<n;i++)
    {
        printf (" %d",a[i]);
    }
    printf("\n");
}

我输入的是 0,4,2,7，但结果是 4,0,7,2。我无法找到此代码的问题。有人可以帮助我吗？

Answer 1

你的for循环应该是:for(j=low;j<high;j++)

看看 Coreman 的算法简介，我认为这是直接出自那里的。

参见http://ideone.com/Ugouy4