快排的各种改进.doc

快排的各种改进 一快排（快速分类）我们在二路选择和二路插入的算法分析中已经知道，用N的操作代价把N个元素排序转化为对两个N/2个元素排序的问题一般可以降低操作次数一半。利用这一原理，对多于1个数据的排序序列分为两个部分，不断切分下去，直到每个排序序列包含的数据少于两个，就不需要再作什么了，因为所有数据已经有序了。所有快排描述的共同特点都是不断切分排序区间，而具体切分的过程可以各具特点，但切分代价应等同与被切分区间的元素个数。具体描述既可以是递归形式也可以是非递归形式。下面看几种各具特色的快排描述。例题 NOIP提高组2007 COUNT原题已经见过，内容略。1 同向切分的递归描述，切分函数传入指针参数形式#include<fstream>using namespace std;ifstream cin("count5.in");ofstream cout("count.out");int a200001;int fd(int *a,int n)int t=a0,i,k=0;for(i=1;i<=n-1;i+)if(ai<t)ak+=ai;ai=ak;ak=t;return k;void kp(int *a,int n)int m;if(n>1)m=fd(a,n);kp(a,m);kp(a+m+1,n-m-1);int main()int n,m,i;cin>>n;for(i=0;i<n;i+)cin>>ai;kp(a,n);an=an-1+1;for(m=i=1;i<=n;i+)if(ai=ai-1)m+;elsecout<<ai-1<< <<m<<endl;m=1;return 0;函数KP和FD配合紧密，分工明确，算是一个较为简捷的描述。2 反向切分，用栈作非递归描述，切分函数传入下标参数#include<iostream>using namespace std;int a100;int fd(int l,int r)int f=-1,z3=r,0,l;int *p=z+1;doif(ap1>ap-1)swap(ap-1,ap1);f=-f;pf+=f;while(p-1>p1);return p1;int main()int i,k,n,z=1;cin>>n;int l100=0,1,r100=0,n;for(i=1;i<=n;i+)cin>>ai;doif(i=lz)<rz)k=fd(i,rz);lz=k+1;l+z=i;rz+=k-1;while(-z>0);for(i=1;i<=n;i+)cout<<ai<< ;cout<<endl;system("pause");return 0;为了复习另一种重要的数据结构队列，下面给出的是用队列描述的非递归快排。其中FD函数的参数形式也采用下标形式。3 同向切分，队列描述的非递归排序#include<iostream>using namespace std;int a3000000;int fd(int l,int r)/找到分点int k=l,t=al;for(int i=l+1;i<=r;i+)if(ai<t)ak+=ai;ai=ak;ak=t;return k;int main()int i,n,m,b1000=1,t=0,w=0;cin>>n;int c1000=n;for(i=1;i<=n;i+)cin>>ai;doif(bt<ct)m=fd (bt,ct);b+w=bt;cw=m-1;b+w=m+1;cw=ct;while(+t<=w);for(i=1;i<=n;i+)cout<<ai<< ;cout<<endl;system("pause");return 0;4 随机化切分对于完全有序或完全反序的数据，这些最直接的切分方式会退化为N平方计算量的算法。但这些描述对绝大多数数据分布又是最快(n*log2(n)的方法之一，可见它们的时间敏感度很高。对作为“比较标准”的数据(fd函数中的a0或al)随机选择常可以防止这种退化。下面仅给出FD函数随机化改进的参考代码int fd(int *a,int n)int p=(rand()*rand()%n;int t=ap,i,k=0;ap=ak;for(i=1;i<=n-1;i+)if(ai<t)ak+=ai;ai=ak;ak=t;return k;5 合并FD与KP的功能，兼顾相同的排序数据进行了随机化处理的快排在一种更为特殊的情况下仍可以退化，这就是所有待排序数据等值。而下面这种把KP和FD合并描述的方法把这种情况也处理得比较合理。#include<iostream>#include<fstream>using namespace std;ifstream fin("kp.in");ofstream fout("kp.out");int a10001;void kp(int l,int r)if(l>=r)return;int m=a(l+r)/2,p=l,q=r;dowhile(ap<m) p+;while(aq>m) q-;if(p<=q) swap(ap+,aq-);while(p<=q);kp(l,q);kp(p,r