一直想好好学习算法，但是就是各种各样的理由颓废了。
首先从排序算法开始，排序算法效率最好的就是快排了，算法的复杂性平均情况下是O(nlgn），最坏情况下是O(n^2)。和partition时标准值的选取以及数列原来的性质有关
现在贴上算法导论上的模板。
#include<cstdio>
#include<cstdlib>
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
int partition(int A[],int p,int r){
int i=p-1;
intx=A[r];
for(int j=p;j<=r-1;++j)
{
if(A[j]<=x){ i=i+1;swap(&A[j],&A[i]);}
}
swap(&A[r],&A[i+1]);
return i+1;
}
void quicksort(int A[],int l,int r)
{
if(l<r){
int p=partition(A,l,r);
quicksort(A,l,p-1);
quicksort(A,p+1,r);
}
}
int main()
{
int A[]={3,5,6,2,9,1};
quicksort(A,0,5);
for(int i=0;i<6;i++)printf("%d\t",A[i]);
system("pause");
return 0;
}
刚才基本大部分默写出来了，就是发现少了一个条件，快排主程序的边界检查，害的我不知道怎么回事出不来结果。
快排首先以某个元素为界，分为两个部分，左部分比该元素值大，右部分小于该元素，然后再分别对左右两个部分进行排序。
最终的是对于所有元素以某个元素为中间值分类，基本思想就是设置两个指针，一个记录目前为止存储的比该值小的指针（将所有小值一起放到左边），另一个记录整个扫描从左到右扫描，若是扫描到了小于该值的原素，则将记录存储指针右移，并将该值与指针右边值互换过来。最后将标记值放到中间，返回该位置指针。
发现了自己曾经写的随机化快速排序，就是partition时，寻找的标准值不再是右边最后一个，二十随机选取，这样才使得在平均情况下性能达到O(nlgn)
#include<cstdio>
#include<cstdlib>
#include<cmath>
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int partition(int A[],int p,int r)
{
int x,i,k,temp;
k=(int)(1.0*(rand()%100)/100*(r-p)+p);
swap(A[k],A[r]);
x=A[r];
i=p-1;
for(int j=p;j<=r-1;j++)
{
if(A[j]<=x){
i++;
swap(A[i],A[j]);
//temp=A[i];A[i]=A[j];A[j]=temp;
}
}
swap(A[i+1],A[r]);
//temp=A[i+1];A[i+1]=A[r];A[r]=temp;
//printf("%d\n",i+1);
return i+1;
}
void quicksort(int A[],int p,int r)
{
if(p<r){
int q=partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}
int main()
{
int n;
scanf("%d",&n);
int *A=new int[n];
int m=n;
while(m--){
scanf("%d",&A[m]);
}
quicksort(A,0,n-1);
m=0;
while(m<n)printf("%d ",A[m++]);
//system("pause");
return 0;
}