c - 快速排序程序提供部分排序的输出

Question

下面以最后一个元素为基准的简单快速排序代码几乎可以工作，但最后一个元素无法排序。有没有想过这个程序哪里出错了？

这是输出:

$a.out
 4 3 5 2 1 3 2 3 //input
 1 2 2 3 3 3 5 4 //output

简单的交换看起来不错

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

嗯..也很好..end 可能有问题？

int partition(int a[],int start,int end){
int pivot = a[end];
int pindex=start;int i;

    for ( i=start; i <= end-1; i++){
       if (a[i] <= pivot){
           swap(&a[i],&a[pindex]);pindex++;
       }
    }
    swap(&a[pindex],&a[pivot]);
    return (pindex + 1);
}

当然看起来不错。

void quicksort(int a[],int start,int end){
int pindex;

    if (start < end){
        pindex = partition(a,start,end-1);
        quicksort(a,start,pindex-1);
        quicksort(a,pindex+1,end);
    }
}

简单的主调用

int main(){
    int a[8] = {4, 3, 5, 2, 1, 3, 2, 3};
    int i=0;

    for(i=0;i<8;i++)
        printf(" %d", a[i]);
    quicksort(a,0,8);
    printf("\n");
    for(i=0;i<8;i++)
        printf(" %d", a[i]);
}

Answer 1

好的几个变化

作为 doptimusprime 指向的返回 pindex

int partition(int a[],int start,int end){
    int pivot = a[end];
    int pindex=start;int i;
    for ( i=start; i <= end-1; i++){
        if (a[i] <= pivot){
            swap(&a[i],&a[pindex]);pindex++;
        }
    }
    swap(&a[pindex],&a[end]);
    return (pindex);
}

相应地调整你的快速排序函数

void quicksort(int a[],int start,int end){
    int pindex;

    if (start < end){
        pindex = partition(a,start,end-1);
        quicksort(a,start,pindex); // no pindex-1
        quicksort(a,pindex+1,end);
    }
}