实现快排最优版本算法上机报告.doc

算法导论第二次上机报告 班级：1403018 姓名：张可心 学号：14030188030 （一）题目一 一、问题 This project requires you to implement an optimized version of quicksort, and compare the performances of the following combinations: Cutoff values from 0 to 50; Take pivot to be the 1st element, random, median of random three, and median of random five. The tests must be done on the following three kinds of inputs: sorted input; reverse-ordered input; random input. The size of input can be taken from 1000 to 10000. The run times must be plotted with respect to the sizes to illustrate the difference. (figure out using excel, matlab in the Report) 二、问题分析 实现快排的最优版本，分别选取第一个数，随机数，三个随机数的中位数，五个随机数的中位数为基数，设置顺序，随机，逆序三种形式，用_qsort(int a[],int p,int r,int number)和Partition(int a[],int p,int r,int number)俩函数进行排序。 三、算法伪代码 void _qsort(a, p, r, number) if pr q=Partition(a,p,r,number) _qsort(a,p,q-1,number) _qsort(a,q+1,r,number) int Partition(int a[],int p,int r,int number) { int x,temp; if(number==1) { temp=p; } else if(number==2) { temp=rand()%(r-p+1)+p; } else if(number==3) { int b[5]; b[1]=rand()%(r-p+1)+p; b[2]=rand()%(r-p+1)+p; b[3]=rand()%(r-p+1)+p; sort(b+1,b+4); temp=b[2]; } else if(number==4) { int b[10]; b[1]=rand()%(r-p+1)+p; b[2]=rand()%(r-p+1)+p; b[3]=rand()%(r-p+1)+p; b[4]=rand()%(r-p+1)+p; b[5]=rand()%(r-p+1)+p; sort(b+1,b+6); temp=b[3]; } else{ temp=p; } x=a[temp]; swap(a[temp],a[p]); int i=r+1; for(int j=r;jp;j--) { if(a[j]=x) { i--; swap(a[i],a[j]); } } swap(a[i-1],a[p]); return i-1; } int main() { int n,a[200000]; cout测试数据：; cinn; for(int i=1;i=n;i++) a[i]=random(51); cout序列的顺序（1顺序；2随机；3逆序）：; int s; cins; if(s==3) sort(a+1,a+1+n,greaterint());//对生成数进行排列 else if(s==1) sort(a+1,a+1+n); else if(s==2){ } else{ } cout确定基数：1,第一个数；2,随机数；3，3个随机数的中位数；4，5个随机数的中位数：; int number; cinnumber; clock_t start,end;//计时 start=clock(); _