数据结构各种排序实验报告.doc

《数据结构各种排序实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1.引言42.需求分析43.详细设计43.1直接插入排序43.2折半排序53.3希尔排序63.4简单选择排序63.5堆排序63.6归并排序73.7冒泡排序94.调试105.调试及检验115.1直接插入排序115.2折半插入排序115.3希尔排序125.4简单选择排序125.5堆排序135.6归并排序145.7冒泡排序146.测试与比较156.1调试步骤156.2结论167.实验心得与分析168.附录178.1直接插入排序178.2折半插入排序188.3希尔排序208.4简单选择排序228.5堆排序238.6归并排序268.7冒泡排序298.8主程序301.需求分析课程题目

2、是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。软件环境：Windows-7操作系统，所使用的软件为c-Free；2.概要设计2.1直接插入排序⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，

3、可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。⑵程序实现及核心代码的注释：for(i=1;ij;--i)r.base[i]=r.base[i-1];//记录后移r.base[j]=temp;//插入到正确的为位置}r.base[r.length]='';2.2折半排序⑴算

4、法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O（n2）。⑵程序实现及核心代码的注释：voidzb(FILE*fp){//对顺序表作折半插入排序for(i=1;i

5、在base[low]到key[high]中折半查找有序插入的位置{m=(low+high)/2;//折半if(temp=high+1;--j)r.base[j+1]=r.base[j];//记录后移r.base[high+1]=temp;//插入}2.3希尔排序⑴算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分割”，而是将分隔某个“增量

6、”的记录组成一个子序列。⑵程序实现及核心代码的注释：for(k=0;k<10;k++){m=10-k;for(i=m;i=0&&temp

7、倒数第二个数和最后一个数比较为止。⑵程序实现及核心代码的注释：for(i=0;ir.base[m])j=m;r.base[i]=r.base[j];//把下标为j的数与i数互换；r.base[j]=temp;}2.5堆排序⑴算法思想：堆排序