快速排序?qū)崿F(xiàn)

/*快速排序算法實(shí)現(xiàn)，快序排序算法最壞復(fù)雜度為O(n^2),平均復(fù)雜度為O(nlgn),而且該比例因子比較少*/

#include<stdio.h>
#include<stdlib.h>


void print(int A[],int len)
{
    int i;
    for(i=0;i<len;i++)
    {
        printf("%d  ",A[i]);
    }
    printf("\n");
}

int quickPart(int A[],int begin,int end)
{
    int key,i,j,temp;
    key=A[end-1];
    i=begin-1;
    for(j=begin;j<end-1;j++)
    {
        if(A[j]<key)
        {
            i++;
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }
    i++;
    temp=A[i];
    A[i]=key;
    A[end-1]=temp;
    return (i);
}


void quickSort(int A[],int begin,int end)
{
    int q;
    if(end>begin)
    {
        q=quickPart(A,begin,end);
        quickSort(A,begin,q);
        quickSort(A,q+1,end);
    }
}


int main()
{
    int  A[8]={2,8,7,1,3,5,6,4};
    quickSort(A,0,8);
    printf("after sort\n");
    print(A,8);
}

posted on 2011-03-22 10:28 周強(qiáng) 閱讀(240) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 算法