[算法练习]快速排序的C语言实现-蒲公英云

[算法练习]快速排序的C语言实现

#include <stdio.h>
void quick_sort(int A[],int p,int r){
    if(p<r){
        int q=partition(A,p,r);
        quick_sort(A,p,q-1);
        quick_sort(A,q+1,r);
    }
}
int times=0;
//basic function of quick sort
int partition(int A[],int p,int r){
    /*    assume A[r] as the benchmark;
        while A[cur] is move from A[p] to A[r]:
        if A[cur] is smaller than A[r],    then exchange A[par] and A[cur];
        A[cur] move to next;
         at last, exchange A[r] and A[par];
         so that A[par] is sorted in the array A[],
         because the numbers before A[par] is smaller than it,
         and the numbers after A[par] is larger than it.
    */
    int cur=p,par=p;
    while(cur<r){
        if(A[cur]<A[r]){
            //exchange A[cur] and A[par] then par++
            int temp=A[cur];
            A[cur]=A[par];
            A[par]=temp;
            par++;
        }
        cur++;
    }
    //exchange A[r] and A[par]
    int temp=A[r];
    A[r]=A[par];
    A[par]=temp;
    printf("\nafter %d times:\t",++times);
    int i;
    for(i=0;i<10-1;i++){
        printf("%d ",A[i]);
    }
    return par;
}
int main(){
    int a[]={3,1,5,12,6,8,11,7,4,15};
    int length=sizeof(a)/sizeof(a[0]);//get length of a[]
    int i;
    printf("before:\t");
    for(i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    quick_sort(a,0,length-1);
    printf("\nafter:\t");
    for(i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    getchar();
}