算法排序问题实验报告

《排序问题求解》实验报告一、算法的基本思想1、直接插入排序算法思想直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1的有序序列。直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n个待排序的数。用伪代码表示直接插入排序算法如下：InsertionSort(A)fori←2tondokey←A[i]//key表示待插入数//InsertA[i]intothesortedsequenceA[1..i-1]j←i-1whilej0andA[j]keydoA[j+1]←A[j]j←j-1A[j+1]←key2、快速排序算法思想快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0]小的数都排在它的位置之后，由此以A[0]最后所在的位置i作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high所指位置起向前搜索，找到第一个小于pivotkey的数，并将其移到低端，然后从low所指位置起向后搜索，找到第一个大于pivotkey的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下：Partition(A,low,high)A[0]←A[low]//用数组的第一个记录做枢轴记录privotkey←A[low]//枢轴记录关键字whilelowhigh//从表的两端交替地向中间扫描whilelowhigh&&A[high]=privotkeydohigh←high-1A[low]←A[high]//将比枢轴记录小的记录移到低端whilelowhigh&&A[low]=pivotkey)dolow←low+1A[high]←A[low]//将比枢轴记录大的记录移到高端A[low]←A[0]//枢轴记录到位returnlow//返回枢轴位置二、算法的理论分析1.直接插入排序算法理论分析从空间来看，直接插入排序只需要一个数的辅助空间；从时间来看，直接插入排序的基本操作为：比较两个关键字的大小和移动记录。先分析一趟直接插入排序的情况。伪代码InsertionSort中while循环的次数取决于待插入的数与前i-1个数之间的关系。若A[i]A[0],则在while循环中，待插入数需与有序数组A[1..i-1]中i-1个数进行比较，并将A[i-1]中i-1个数后移。则在整个排序过程（进行n-1趟插入排序）中，当待排序数组中数按非递减有序排列时，则需进行数间比较次数达最小值n-1,数不需要移动；反之，当待排序数组中数按非递增有序排列时，总的比较次数达最大值(n+2)(n-1)/2，数移动的次数也达到最大值(n+4)(n-1)/2。若待排序数组是随机的，即待排序数组中的数可能出现的各种排序的概率相同，则我们可取上述最小值和最大值的平均值，作为直接插入排序时所需进行数间的比较次数和数的移动次数，约为n^2/4。因此直接插入排序算法，在最佳情况下的时间复杂度是O(n)，在最坏情况下的时间复杂度为O(n^2)。2.快速排序算法理论分析下面我们来分析快速排序的平均时间性能。假设T(n)为对n个记录A[1..n]进行快速排序所需时间，则由算法QuickSort可见：其中，Tpass(n)为对n个记录进行一趟快速排序Partition（A,1,n）所需的时间，从一趟快速排序算法可见，其和记录数n成正比，可以用cn表示（c为某个常数）；T(k-1)和T（n-k）分别为对A[1..k-1]和A[k+1..n]中记录进行快速排序QuickSort（A,1,k-1）和QuickSort（A,k+1,n）所需时间。假设待排序列中记录是随机排列的，则在一趟排序之后，k取1至n之间任何一值的概率相同，快速排序所需时间的平均值则为Tavg(n)=knInn，其中n为待排序序列中记录的个数，k为某个常数。通常，快速排序被认为是，在所有同数量级（O(nlogn)）的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n^2)。三、试验分析1、试验环境WIN32系统，VC6.02、程序的执行1)由函数datagenetare()生成20000个在区间[1,100000]上的随机整数，并将随机整数保存到数组num[]，接着调用函数WriteFile()将这些数输出到外部文件data.txt中。2)调用函数ReadFile()从data.txt中读取数据，并将其保存到数组num1[]中。接着对数组num1进行直接插入排序，并计算和记录其运行时间。最后，调用函数WriteFile()将直接插入排序的结果写入resultsIS.txt，并记录运行时间为TimeIS。3)调用函数ReadFile()从data.txt中读取数据，并将其保存到数组num2[]中。接着对数组num2进行快速排序，并计算和记录其运行时间。最后，调用函数WriteFile()将快速排序的结果写入resultsQS.txt，并记录运行时间为TimeQS。3、试验数据当N=20000时：当N=30000时：当N=40000时：当N=50000时：当N=60000时：当N=70000时：当N=80000时：4、实验结果分析20000300004000050000600007000080000插入排序0.3250.7191.3972.1993.054.5715.46快速排序0.0030.0050.0080.010.0120.0110.013做出折线统计图四、试验心得通过本次试验首先对在C++下的文件操作有了一定的深入认识，对于快速排序和插入排序的时间有了相当清晰且一目了然的认识，并且从原理上明白了快速排序的快的原因，对各种排序算法的优劣性有了全局的认识！五、实验代码#includeiostream#includectime#includecstdlib#includefstream#includestringusingnamespacestd;constintNumS=80000;voiddatagenetare(intnum[],intn);//产生随机数，保存到数组numvoidWriteFile(intnum[],charname[],intn);//输出数组num到data.txt文件voidReadFile(intnum[],charname[]);//读取名为name文件中的数据，保存到数组numvoidQuickSort(intarr[],intn);//将数组arr[]中数据快速排序voidInsertionSort(intarr[],intn);//将数组arr[]中数据直接插入排序intmain(){int*num=(int*)malloc(sizeof(int)*NumS);int*num1=(int*)malloc(sizeof(int)*NumS);int*num2=(int*)malloc(sizeof(int)*NumS);clock_tstart_time1,end_time1,start_time2,end_time2;doubletimeQS=0,timeIS=0;coutCreateNumSrandomnumbersfrom1to100000endl;datagenetare(num,NumS);//产生随机数，保存到数组numWriteFile(num,data.txt,NumS);//输出数组到data.txt文件cout.precision(6);//设置浮点数的显示精度cout.setf(ios_base::showpoint);//输出末尾的//直接插入排序的分析ReadFile(num1,data.txt);//读取data.txt中的数据，保存到数组num1cout\nInsertionSortStart....\n;start_time1=clock();//开始计时InsertionSort(num1,NumS);//直接插入排序数组num1中的数据end_time1=clock();//结束计时timeIS=(double)(end_time1-start_time1)/CLOCKS_PER_SEC;coutTheTime-comsuptioninInsertionSortistimeISseconds!\n\n;//输出运行时间WriteFile(num1,resultsIS.txt,NumS);//排序后的数据输出到resultQS.txt//输出运行时间timeIS到resultsIS.txtofstreamocout;ocout.open(resultsIS.txt,ios::app);if(ocout.good())//打开resultsIS.txt{ocout\nTheTime-comsuptioninInsertionSortistimeISseconds\n;ocout.close();}else{cout\nCannotopenresultsIS.txt!\n;exit(1);//异常退出}//快速排序的分析ReadFile(num2,data.txt);//读取data.txt中的数据，保存到数组num2[]coutQuickSortStart.....\n;start_time2=clock();//开始计时QuickSort(num2,NumS);//快速排序数组num中的数据end_time2=clock();//结束计时timeQS=(double)(end_time2-start_time2)/CLOCKS_PER_SEC;coutTheTime-comsuptioninQuickSortistimeQSseconds:\n;//输出运行时间WriteFile(num2,resultsQS.txt,NumS);//排序后的数据输出到resultQS.txt//输出运行时间timeQS到resultsQS.txtocout.open(resultsQS.txt,ios::app);if(ocout.good())//打开resultsIS.txt{ocout\nTheTime-comsuptioninQuickSortistimeQSseconds\n;ocout.close();}else{cout\nCannotopenresultsQS.txt!\n;exit(1);//异常退出}return0;}voiddatagenetare(int*num,intn){inti;srand((unsigned)time(0));//srand()种子发生器函数，还有rand()随机数生成器函数for(i=0;in;i++)//产生个到之间的随机数num[i]=rand()%9999+1;printf(\n);}//将数组中的数据输出到文件voidWriteFile(int*num,charname[],intn){ofstreamocout;ocout.open(name,ios::trunc);inti=0;if(ocout.fail())exit(1