课程设计——内部排序算法比较

《课程设计——内部排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内部排序算法比较需求分析各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。待排序表的表长不少于100，为方便起见，我们令表长等于100，用5组随机的数据排序的结果作比较。．概要设计2.1可能排序表的抽象数据类型定义：ADTOrderableList｛数据对象：D=｛

2、∈IntegerSet，i=1，2，……，n，n≥0｝数据关系：R

3、1=｛<,

4、,∈D,i=2,……n｝基本操作：InitList（n）操作结果：构造一个长度为n，元素值依次为1，2，……，n的有序表。RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False，将表置为逆序或正序，然后将表进行d（0≤d≤8）级随机打乱。d为0时表不打乱，d越大，打乱程度越高。RecallList（）操作结果：恢复最后一次用RandomizeList随机大乱的可排序表。ListLength（）操作结果：返回可排序的长度。18内部排序算法比较ListEmpty（）操作结果：若

5、可排序表为空表，则返回True，否则返回False。BubbleSort（&c，&s）操作结果：进行冒泡排序，返回关键字比较次数c和移动次数s。InsertSort（&c，&s）操作结果：进行插入排序，返回关键字比较次数c和移动次数s。SelectSort（&c，&s）操作结果：进行选择排序，返回关键字比较次数c和移动次数s。QuickSort（&c，&s）操作结果：进行快速排序，返回关键字比较次数c和移动次数s。ShellSort（&c，&s）操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。HeapSort（&c，&s）操作结果：进行堆排序，返回关

6、键字比较次数c和移动次数s。ListTraveres（visit()）操作结果：依次对L中的每个元素调用函数visit（）。｝ADTOrderableList2.2本程序包含两个模块：2.2.1主程序模块：voidmain(){初始化；do{接受命令；处理命令；}while（"命令"!="退出"）；}18内部排序算法比较2.2.2可排序表单元模块：——实现可排序表的抽象数据类型;主程序模块↓↓可排序表单元模块详细设计3.1直接插入排序直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已牌号序的有序表中，从而得到一个新的、记录数增1的有序表。其算

7、法如下：voidinsertsort(sqlistb,intn){inti,j;ints=0,t=0;for(i=2;i

8、排序，其算法如下：voidBInsertSort(int*data,long*p_movetime,long*p_comparetime){inti,j,amount,low,high,m;*p_movetime=*p_comparetime=0;amount=*data;for(i=2;i<=amount;++i){*(data)=*(data+i);(*p_movetime)++;low=1;high=i-1;while(low<=high){(*p_comparetime)++;m=(low+high)/2;(*p_comparetime)++;//针对

9、于接下来的*(data)和*(data+m)的比较if(*(data)<*(data+m))high=m-1;elselow=m+1;18内部排序算法比较}for(j=i-1;j>=high+1;--j){*(data+j+1)=*(data+j);(*p_movetime)++;}*(data+high+1)=*(data);(*p_movetime)++;}}3.3二路插入排序二路插入排序是在折半插入排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。算法如下:voidTwoWaySort(int*data,long*

10、p_movetime,long*p_c