排序算法的思想呢,我看了许多,觉得比较生动的是:挖坑填坑再分治。
void QuickSort(int l,int r){
if(l>=r)return;
int i=l,j=r,key=a[i];
while(i<j){
while(a[j]>=key&&i<j) j--;
a[i]=a[j];
while(a[i]<=key&&i<j) i++;
a[j]=a[i];
}
a[i]=key;
QuickSort(l, i-1);
QuickSort(i+1, r);
}
调用:
QuickSort(1,n); //数组a[],长度为n
另一种写法:
int Partition(int A[],int p,int q){
int x=A[p];
int i=p;
for(int j=p+1;j<=q;++j)
if(A[j]<=x){
++i;
int t=A[i];A[i]=A[j];A[j]=t;
}
int t=A[i];A[i]=A[p];A[p]=t;
return i;
}
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);
}
}
性能分析:
C为比较次数,M为移动次数。
最坏情况:$C_{max}=(n-1)+(n-2)+..+1=n(n-1)/2$,$M_{max}\leq C_{min}$,$O(n^2)$
最好情况:$C_{min}\leq O(nlgn)$,$M_{min}\leq C_{min}$,$O(nlog_2n)$
平均 $ T_{avg}(n)=kn ln(n)$
k为某个常数,n为元素个数。
辅助空间:因为是递归的,所以需要栈。(如果是全局的数组a,就不需要)
最好情况:$O(log_2n)$
最坏情况:$O(n)$
算法改进:
合理选择枢轴:三者取中(选择a[1],a[n]和a[(n+1)/2]的中位数),随机产生。
稳定性:
是非稳定性排序。如2,2',1,排序后是1,2',2。