排序算法实验报告USTC

《排序算法实验报告USTC》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告一、实验目的在计算机科学与数学中，排序算法是一种基本并且常用的算法，一个排序演算法是一种能将一串资料依照特定排序方式的一种演算法。有效的排序演算法在一些演算法中是重要的，如此这些演算法才能得到正确解答。排序演算法也用在处理文字资料以及产生人类可读的输出结果。由于实际工作屮处理的数量巨大，所以排序算法对算法本身的速度要求很高。通过实现相关一些排序算法，加深对于算法知识的理解与学习。二、实验题目要求实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法，并比较这些算法的性能。三、实验要求(―)在随机产生的空间大小分别为N二10,1000,10000,1

2、00000的排序样本(取值为[0,1])上测试以上算法。(-)结果输出：1)N二10时，排序结果。2)21000,10000,100000时，对同一个样本实例，不同排序完成所需的时间。3)N二1000,10000,10000013寸，每个排序用不同的样本多试验几次(最低5次)得出平均时间，比较不同排序算法所用的平均时间。四、实验内容♦各种排序算法相关代码的实现及其原理说明如下:1.合并排序3738394041424344454G474849505152535455565758596061626364656667€86970//合并排序中的舍并篡法MergevoidM

3、erge(floatarray【].intstart,intmid,intend,intlenEHfloattez?>l(length];floatter?>2(length);intnl,n2;nl«mid・start+1;n2=end-mid;//备份前斗刖分数组至heirpl数统中for(inti=0;i

4、n5>2[n2]=12000,V运万丙部分数运士無个元盍.仁后歛到弋应E：垃査去forintk=starr,i=0rj=0;k<-end;k++)□{if[i]<■temp2[j])□{array[k]-cempl[i];i++；-}else□{array[k]=remp2[j];j++；}-}丨}}I//合并挫序voidMergeSort(floatarray[]rintstart,intendrintlength曰{if(start

5、//对前主部分进行合并捧庆MergeSortarray,start,irl

6、ength);

7、//对后M部分送行合并样序MergeSortarray,end,length';

8、/盪轻Zg色三迭舍并三迢分別捉芳于巧两圧分妄绸Mergearray,szarz,i,end,length>;■}L}I/*//扬入排宇voidInsertSort:floatarray[]rintlength)intifj；floatkey;for(i-1;ikey;j--){arraytj+1]=array[jJ;}//在合适位査安歛当前元素ar

9、raytj+1)=key;对于合并排序，算法过程说明如下：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制冋R[1ow..high]中。合并过程屮，设置i,j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1W中，然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加lo重复这一过程肓至两个输入的子文件有一个已全部复制完毕，此时将另一非空的子文件中剩余记

10、录依次复制到R1中即可。2•插入排序//插入排序voidInsertSort(floatarray[]zintlength)3{intirj；floatkey;for(i=1;i=0&&array[j]>key;j--)3{array[j+1]=array!j];_}array[j+1]=key;-}L}关于直接插入排序的算法说明如2假设待排序的记录存放在数组R[l..n]中。初始时,R[l]自成1个有序区,无序区为R[2..n]0从i=2起直至i=n为止，依次将R[i]插入当前的有序