数据结构试验报告——各种内排序算法的实现及性能比较

实验报告（2010/2011学年第2学期）课程名称数据结构——使用C++语言描述实验名称各种内排序算法的实现及性能比较实验时间2011年5月27日指导单位计算机科学与技术系指导教师学生姓名班级学号学院(系)专业一．实验目的和要求内容：验证教材的各种内排序算法。分析各种排序算法的时间复杂度。要求：使用随机数产生器产生大数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。二．实验环境（实验设备）VisualC++6.0三．实验原理及内容//selectsort.h#includeiostream.h//简单选择排序templateclassTvoidSelectSort(TA[],intn){intsmall;for(inti=0;in-1;i++){//执行n-1趟small=i;for(intj=i+1;jn;j++)if(A[j]A[small])small=j;Swap(A[i],A[small]);}}Insertsort.h#includeiostream.h//直接插入排序templateclassTvoidInsertSort(TA[],intn){for(inti=1;in;i++){//执行n-1趟实验名称各种内排序算法的实现及性能比较指导老师实验类型设计实验学时4实验时间2011.5.27intj=i;Ttemp=A[i];while(j0&&tempA[j-1]){A[j]=A[j-1];j--;}A[j]=temp;}}/*ok!*/Bubblesort.h#includeiostream.htemplateclassTvoidBubbleSort(TA[],intn){inti,j,last;i=n-1;while(i0){last=0;for(j=0;ji;j++)if(A[j+1]A[j]){Swap(A[j],A[j+1]);last=j;}i=last;}}Quicksort.h#includeiostream.h//改进的快速排序templateclassTvoidquick(TA[],intn){int*a;//用数组保存待排序的子序列的上、下界inttop=0,right,left,j;//left和right为待排序a=newint[n];if(a==NULL)return;a[top++]=0;a[top++]=n-1;//以初始序列为待排序序列开始改进的快速排序//lcfor(j=0;a[j]!=NULL;j++)//循环到数组元素为空{left=a[j++];right=a[j];//每次按序从数组中取出两个元素作为待排序序列的上、下界if(leftright)Swap(left,right);//如果下界大于上界，交换上、下界if(right-left15)InsertSortExt(A,left,right);//若元素较少调用插入排序else{a[top++]=left;a[top++]=QuickSort(A,left,right)-1;a[top++]=a[top-2]+2;a[top++]=right;//否则将低、高端序列上、下界依次保存到数组中}}}templateclassTintQuickSort(TA[],intleft,intright)//用于改进的快速排序的原始快速排序方法{inti,j;if(leftright){i=left;j=right+1;do{doi++;while(A[i]A[left]);doj--;while(A[j]A[left]);if(ij)Swap(A[i],A[j]);}while(ij);Swap(A[left],A[j]);returnj;}return0;}templateclassTvoidInsertSortExt(TA[],intleft,intright)//用于快速排序的直接插入排序方法{for(inti=left+1;iright;i++){//执行n-1趟intj=i;Ttemp=A[i];//待插入元素存入临时变量while(j0&&tempA[j-1]){//从后往前查找插入位置A[j]=A[j-1];j--;//A[j-1]元素后移，j指针前移}A[j]=temp;//待插入元素存入找到的插入位置}}Mergesort.h#includeiostream.h//两路合并的C++程序templateclassTvoidMerge(TA[],inti1,intj1,inti2,intj2){//i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界T*Temp=newT[j2-i1+1];//分配能存放两个子序列的临时数组inti=i1,j=i2,k=0;//i,j是两个子序列的游动指针，k是Temp的游动指针while(i=j1&&j=j2)if(A[i]=A[j])Temp[k++]=A[i++];elseTemp[k++]=A[j++];while(i=j1)Temp[k++]=A[i++];while(j=j2)Temp[k++]=A[j++];for(i=0;ik;i++)A[i1++]=Temp[i];delete[]Temp;}//合并排序的C++程序templateclassTvoidMergeSort(TA[],intn){inti1,j1,i2,j2;//i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界intsize=1;//子序列中元素个数，初始化为1。while(sizen){i1=0;while(i1+sizen){i2=i1+size;j1=i2-1;if(i2+size-1n-1)j2=n-1;elsej2=i2+size-1;Merge(A,i1,j1,i2,j2);i1=j2+1;}size*=2;}}Heapsort.h#includeiostream.h//AdjustDown函数templateclassTvoidAdjustDown(TA[],intr,intj){intchild=2*r+1;Ttemp=A[r];while(child=j){if((childj)&&(A[child]A[child+1]))child++;if(temp=A[child])break;A[(child-1)/2]=A[child];child=2*child+1;}A[(child-1)/2]=temp;}//堆排序的C++程序templateclassTvoidHeapSort(TA[],intn){for(inti=(n-2)/2;i-1;i--)AdjustDown(A,i,n-1);//构造最大堆for(i=n-1;i0;i--){Swap(A[0],A[i]);AdjustDown(A,0,i-1);}}Meau.h#includeiostream.h#includestdio.h#includestdlib.h#includetime.h#includeselectsort.h#includeinsertsort.h#includebubblesort.h#includequicksort.h#includemergesort.h#includeheapsort.h#defineSIZE400#defineTIMES1000templateclassTclassMenu{public:voidprintmenu();voidselectsort();//简单选择排序voidinsertSort();//直接插入排序voidbubbleSort();//冒泡排序voidquickSort();//快速排序voidmergeSort();//两路合并排序voidheapSort();//堆排序voidchildmenu();//子菜单1voidchildmenu2();//子菜单2voidswitcha();private:inta,b,c;};templateclassTvoidMenuT::printmenu(){cout--------------------------------------------------------endl;cout内排序测试系统endl;cout--------------------------------------------------------endlendlendl;cout1.简单选择排序endl;//okcout2.直接插入排序endl;//okcout3.冒泡排序endl;//okcout4.快速排序endl;//okcout5.两路合并排序endl;//okcout6.堆排序endl;//okcout7.退出endl;coutPS：测试用的数组元素为SIZE时间为重复运行TIMES次的时间（包括了产生数据与析构的时间）endl;this-switcha();}templateclassTvoidMenuT::childmenu(){cout--------------------------------------------------------endl;cout1.最好情况endl;cout2.最坏情况endl;cout3.平均情况endl;cout4.返回主菜单endl;cinb;if(b==4)this-printmenu();}templateclassTvoidMenuT::childmenu2(){cout--------------------------------------------------------endl;cout1.原始算法endl;cout2.改进算法endl;cout3.返回主菜单endl;cinc;if(c==3)this-printmenu();}templateclassTvoidMenuT::switcha(){//coutokendl;cina;switch(a){case1:this-selectsort();break;//okcase2:this-insertSort();break;//okcase3:this-bubbleSort();break;//okcase4:this-quickSort();break;//okcase5:this-mergeSort();break;//okcase6:this-heapSort();break;//okcase7:exit(1);break;default:couterrorendl;this-printmenu();break;}};templateclassTvoidprintout(TA[],intn)//打印数组，测试时用{for(inti=0;in;i++)coutA[i];coutendl;}templateclassTT*producedate(intx)//产生顺序，逆序，随机的数组{inti;T*A=newT[SIZE];switch(x){case1:for(i=0;iSIZE;i++)A[i]=i;returnA;//顺序break;case2:for(i=SIZE;i0;i--)A[i-1]=SIZE-i;returnA;//逆序break;case3:srand(time(NULL));for(i=0;iSIZE;i++){A[i]=rand()%1000+1;}