排序(数据结构课程设计)

1、数据结构课程设计实验报告题目：排序（必做题）姓名： 学号：指导老师： 时间：2015.09.03目录一、设计内容和要求3二、算法思想描述31.希尔排序32.快速排序33.堆排序44.归并排序75.性能分析8三、程序结构10四、结果与分析10五、收获与体会12一、 设计内容和要求设计内容：排序算法的实现与比较要求：编程希望实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入数据文件，然后读数据文件，分别采用不同的排序方法进行排序，将结果存入文件中。二、 算法思想描述1. 希尔排序先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对

2、全体记录进行一次直接插入排序。图解：2. 快速排序首先选一个枢轴k（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于枢轴k，后一部分记录的关键码均大于或等于枢轴k，然后分别对这两部分重复上述方法，直到整个序列有序。经过一次划分后2区1区枢轴k再对1、2区分别再进行快速排序3. 堆排序筛选：假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即rk+1 rm满足堆的条件），则筛选算法用伪代码可描述为：图解：堆排序：堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将

3、它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。（1） 用大根堆排序的基本思想 先将初始文件R1.n建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1（即堆顶）和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1

4、.n-2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。直到无序区只有一个元素为止。（2） 大根堆排序算法的基本操作： 初始化操作：将R1.n构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R1和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。注意： 只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止图解：4. 归并排序归并排序是一种借助“归并”进行排

5、序的方法，其主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。归并是将两个或两个以上的有序序列合并成一个有序序列的过程。基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，直至得到一个长度为n的有序序列为止。5. 性能分析n 由于计算机实现的排序算法，没有标准的数据交换操作，因此用交换次数作为衡量性能的标准很不准确，这里计算移动次数，即内存发生赋值操作则计数一次。n 即使计算了内存的拷贝操作，实际的性能仍与很多因素关联，因此，程序作了耗时测试，研究在排序表数据结构发生变

6、化时，算法消耗的时间随之变化的规律。n 数据量对性能的影响：u 为降低其他因素的影响，每组数据均按比例平均分布。u 如：100个数据则分布在0，100，500个数据则分布在0，500。运行结果：希尔快速堆归并比较次数103037502150324262508220100764703124853950063865078846438481000149161111918850872350001111947461011772255235100002609881629682555521204241500040672325177740050618934320000606881347716550780260

7、82925000809050474661705064334093移动次数102419733450233138531286100500303118367250048042109707344881000112924688150769976500084389285718707861808100002031866186118422513361615000325076974592849832086162000048234213401238842928723225000659156169596493845367232图表表示：n 直观分析：两张折线图可以看出，数据量在1000以内，各排序算法各方面性能都几

8、乎一致。数据增多至一定值时，各算法开始各自的稳定增长，但相互之间有明显差别。100015000时，希尔和堆排序仍有重叠迹象，15000后，按照希尔、堆、快速、归并的顺序，可近似认为前者斜率分别是后者的2倍。n 理论性能：移动操作时间、空间复杂度均远超过比较操作，因此，以移动次数衡量，快速排序性能最好。综合比较、移动次数来看，仍然是快速排序性能最好，归并次之，但这仅是理论分析，实际运行时，还要考虑诸多因素，如归并排序大量的递归函数调用及数据移动操作，会占用过多的CPU及时间，极大的影响性能。三、 程序结构四、 结果与分析当测试10000个数据时2次测试结果如下：当测试100000个数据时5次测试结果如下，可看出快速排序是4个中相对最快的排序方法：五、 收获与体会1. 通过产生随机数文件，我