/*快速排序算法實現，快序排序算法最壞復雜度為O(n^2),平均復雜度為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);
}