/*快速排序算法实现，快序排序算法最坏复杂度为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);
}