题目：排序（必做题）姓名：学号：指导老师：时间：3目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc428954653"一、设计内容和要求PAGEREF_Toc428954653\h3HYPERLINK\l"_Toc428954654"二、算法思想描述PAGEREF_Toc428954654\h3HYPERLINK\l"_Toc428954655"1.希尔排序PAGEREF_Toc428954655\h3HYPERLINK\l"_Toc428954656"2.快速排序PAGEREF_Toc428954656\h3HYPERLINK\l"_Toc428954657"3.堆排序PAGEREF_Toc428954657\h4HYPERLINK\l"_Toc428954658"4.归并排序PAGEREF_Toc428954658\h7HYPERLINK\l"_Toc428954659"5.性能分析PAGEREF_Toc428954659\h8HYPERLINK\l"_Toc428954660"三、程序结构PAGEREF_Toc428954660\h10HYPERLINK\l"_Toc428954661"四、结果与分析PAGEREF_Toc428954661\h10HYPERLINK\l"_Toc428954662"五、收获与体会PAGEREF_Toc428954662\h12设计内容和要求设计内容：排序算法的实现与比较要求：编程希望实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入数据文件，然后读数据文件，分别采用不同的排序方法进行排序，将结果存入文件中。算法思想描述希尔排序先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。图解：快速排序首先选一个枢轴k（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于枢轴k，后一部分记录的关键码均大于或等于枢轴k，然后分别对这两部分重复上述方法，直到整个序列有序。经过一次划分后2区1区枢轴k再对1、2区分别再进行快速排序堆排序筛选：假设当前要筛选结点的编号为k，堆中最后一个结点的编号为m，并且结点k的左右子树均是堆（即r[k+1]~r[m]满足堆的条件），则筛选算法用伪代码可描述为：图解：堆排序：堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。用大根堆排序的基本思想①先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区②再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区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]调整为堆。……直到无序区只有一个元素为止。大根堆排序算法的基本操作：①初始化操作：将R[1..n]构造为初始堆；②每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。注意：只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止图解：归并排序归并排序是一种借助“归并”进行排序的方法，其主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。归并是将两个或两个以上的有序序列合并成一个有序序列的过程。基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，