《中国科技大学算法导论-第一次实验报告.pdf》由会员分享，可在线阅读，更多相关《中国科技大学算法导论-第一次实验报告.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 中国科技大学算法导论-第一次实验报告-作者:_ -日期:_ 快速排序实验报告 一、题目 当输入数据已经“几乎”有序时，插入排序速度很快。在实际应用中，我们可以利用这一特点来提高快速排序的速度。当对一个长度小于 k 的子数组调用快速排序时，让它不做任何排序就返回。当上层的快速排序调用返回后，对整个数组运行插入排序来完成排序过程。试证明：这一排序算法的期望时间复杂度为 O（nk+nlg（n/k）。分别从理论和实践的角度说明我们应该如何选择 k？二、算法思想 当输入数据已经“几乎”有序时，插入排序速度很快。当对一个长度小于 k 的子数组调用快速排序时，让它不做任何排序就返回。当上层的快速排序调用返
2、回后，对整个数组运行插入排序来完成排序过程。累加 k 的值，计算出当 k 为不同值时算法运行的时间，来算出当 k 大约为什么值时运行的时间最短，并与传统的快速排序算法的运行时间进行比较。三、实验结果 输入 100 个不同的整数值，选取不同的 k 的值，观察所用时间 四、实验分析 理论上看，k 的值选取为 20 到 25 较好；但是，从实际上来看，当 k 为 50 左右时间为 39 毫秒，最少，但不同的时刻运行后的时间都不相同，而且不同的输入时刻的运行时间也不相同，当数据较大时候，对 k 的值的选取有会有所不同，同时不同性能的机器对测试结果也不同，所以对于 k值的选取没有固定的数值。#inclu
3、de#include using namespace std;#define M 40 void swap(int*a,int*b)int tem;tem=*a;*a=*b;*b=tem;int partition(int v,const int low,const int high)int i,pivotpos,pivot;pivotpos=low;pivot=vlow;for(i=low+1;i=high;+i)if(vipivot)pivotpos+;if(pivotpos!=i)swap(vi,vpivotpos);vlow=vpivotpos;vpivotpos=pivot;/cou
4、tthe partition function is calledn;return pivotpos;/*void QuickSort(int a,const int low,const int high)int item;if(lowhigh)item=partition(a,low,high);QuickSort(a,low,item-1);QuickSort(a,item+1,high);*/void QuickSort(int a,const int low,const int high)int item;if(high-low=M)return;if(lowhigh)item=par
5、tition(a,low,high);QuickSort(a,low,item-1);QuickSort(a,item+1,high);/coutthe QuickSort is calledendl;void InsertSort(int a,const int low,const int high)int i,j;int tem;for(i=1;i=0&temaj)aj+1=aj;j-;aj+1=tem;/coutthe InsertSort is calledendl;void HybridSort(int a,const int low,const int high)QuickSort
6、(a,low,high);InsertSort(a,low,high);coutthe HybidSort is calledendl;int main()int i,a100;/int*a=NULL;long int t;struct timeb t1,t2;/*coutplease input the number of the element:n;a=(int*)malloc(n*sizeof(int);coutplease input every element:endl;*/for(i=0;i100;i+)ai=i+10;/QuickSort(a,0,n-1);ftime(&t1);
7、HybridSort(a,0,99);cout after sorted quickly,the result isendl;for(i=0;i100;i+)coutai;if(i%10=0)coutendl;coutendl;ftime(&t2);t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);/*计算时间差*/printf(k=%d 用时%ld毫秒n,M,t);/coutthe memory of array a is freeendl;/free(a);coutnendl;return 0;-THE END,THERE IS NO TXT FOLLOWING.-