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

《排序(数据结构课程设计)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。（1）用大根堆排序的基本思想①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区②再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序

4、区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。……直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作：①初始化操作：将R[1..n]构造为初始堆；②每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。注意：②只需做n-1趟排序，选出较大的n-1个

5、关键字即可以使得文件递增有序。②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止12/12图解：1.归并排序归并排序是一种借助“归并”进行排序的方法，其主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。归并是将两个或两个以上的有序序列合并成一个有序序列的过程。基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，

6、……，直至得到一个长度为n的有序序列为止。12/121.性能分析n由于计算机实现的排序算法，没有标准的数据交换操作，因此用交换次数作为衡量性能的标准很不准确，这里计算移动次数，即内存发生赋值操作则计数一次。n即使计算了内存的拷贝操作，实际的性能仍与很多因素关联，因此，程序作了耗时测试，研究在排序表数据结构发生变化时，算法消耗的时间随之变化的规律。n数据量对性能的影响：u为降低其他因素的影响，每组数据均按比例平均分布。u如：100个数据则分布在[0，100]，500个数据则分布在[0，500]。运行结果：希尔快速堆归并比较次数103037502150324262508

7、22010076470312485395006386507884643848100014916111191885087235000111194746101177225523510000260988162968255552120424150004067232517774005061893432000060688134771655078026082925000809050474661705064334093移动次数10241973345023313853128610050030311836725004804210970734488100011292468815076