数据结构作业报告.doc

华南农业大学信息学院 设计性、综合性实验 起止日期:2002 -2003 学年第一学期系别01计算机班级01计算机（4）班小 组 名实验题目实现各种排序算法并分析与比较设计性 综合性分工情况学号姓名分工得分2001374424吴晓辉算法思想，程序设计，调试并通过程序，写报告自我评价本程序完成实验要求的全部功能直接插入排序、shell排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。在实验过程中，积极配合本团队分工合作的精神，努力学习，总算不负众望，将程序编好，在此，我更想感谢的是老师的教导，在她的帮助下，我才顺利完成了本次的任务。教师评语l a-能够分工合作，体现良好的团队协作精神，完成实验要求的全部功能并运行通过，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。l b-能够分工合作，体现良好的团队协作精神，完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述清晰完整。l c-完成实验要求的大部分功能，实验报告良好。l d-未按时完成实验，或者抄袭。 教师签名： 一、需求分析本程序要求用函数实现如下算法：（1） 直接插入排序（2） 希尔排序（3） 冒泡排序（4） 快速排序（5） 选择排序（6） 堆排序（7） 归并排序（8） 基数排序并定量分析各种排序算法在正序、逆序、少量、大量情况下的运行效率。1输入的形式和输入值的范围全部待排序的数据都是整形数据,范围为0 65535，并且为无序数列。2 输出的形式输出排好序的数列。3 程序所能达到的功能：本程序可以从磁盘文件读入数据，将其进行8种方法排序，程序代码清晰，结果输出简单。4 测试数据二、概要设计程序通过一个主函数（main）调用所有排序方法，大致的函数调用关系如下： 希尔排序直接插入排序选择排序冒泡排序主函数堆排序快速排序归并排序 基数排序二、 算法表述三、详细设计说明1直接插入排序假设待排序的记录存放在数组r0.n-1中，排序过程的某一中间时刻，r被划分成两个子区间r0i-1和ri.n-1，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。直接插入排序的基本操作是将当前无序区的第1个记录ri插入到有序区r0.i-1中适当的位置，使r0i变为新的有序区。2 希尔排序先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组，所有距离为d1的倍数的记录放在同一组中，在各组内进行直接插入排序；然后取第二个增量d2d1，重复上述的分组和排序，直至增量d1，即所有记录放在同一组中进行直接插入排序为止。3 冒泡排序通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录逐渐向上升。整个算法是从最下面的记录开始，对每两个个相邻的关键字进行比较，且使关键字小的记录换至关键字较大的位置，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在剩下的记录中找关键字次小的记录，并把它换至第二个位置上。依此类推，一直到所有记录都有序为止。4 快速排序在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，数据序列被此记录分割成两部分。所有比它大的记录放置在后一部分，所有比它小的记录放置在前一部分，并把该记录排在这两部分之间，这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程，直至每部分内只有一个记录为止。简而言之，每趟使表的第一个元素入终位，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为1。5 选择排序基本思想：第i趟排序开始时，当前有序区和无序区分别为r0.i-1和rin-1,该趟排序则是从无序区中选出关键字最小的记录rk,它与无序区的第一个记录ri交换,使r0i和ri+1n分别变为新的有序区和无序区。因为每趟排序使有序区中增加一个记录，且有序区的记录均不大于无序区中记录的关键字，即第i趟排序之后r0i的所有关键字等于ri+1.n-1中的所有关键字,所以进行n-1趟之后有r0.n-2的所有关键字小于等于其后所有关键字,也就是说,经过n-1趟排序后,整个表r0.n-1递增有序.6 堆排序堆排序是在排序过程中，将顺序表中存储的数据看成是一棵完全而叉树，利用完全二叉树中双亲结点和孩子结点之间的内在联系来选择关键字最小记录。具体做法是：把待排序的表的关键字存放在数组r1n之中，将r看成一棵二叉树，每个结点表示一个记录，原表的第一个记录r1作为二叉树的根，以下各记录r2.n依次逐层从左到右顺序排序，构成一棵完全二叉树，任意结点ri的左孩子是r2i+1，右孩子是r2i+2，双亲是ri/2。7 归并排序归并排序是多次将两个或两个以上的有序表合并成一个新的有序表以两个有序表的合并为例：每次从两个有序表中取出一个记录进行关键字的比较，将较小的放入一个临时数组，最后将各段中余下的部分直接复制到临时数组。这样临时数组就是一个有序表。8基数排序 以r为基数的最低位优先基数排序的过程是：假设线形表由结点序列a0，a1，a(n-1)构成每个结点aj的关键字由d元组（）。在排序过程中使用r个队列q0，q1，.qr-1。排序过程如下： 对i=0，1，.，d-1，依次做一次“分配”收集”（其实就是一次稳定的排序过程）。 分配：开始时，把q0，q1，qr-1各个队列置成空队列，然后依次考察线性表中的每一个结点aj（j=0，1，n-1），如果aj的关键字，就把aj放进qk队列中。收集：把q0，q1，.，qr-1各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。int asize; 重要数组，用于存放数据int count,show,row; 记录所需要的信息，如换行等等load() 用于从磁盘读取数据insertion() 插入排序shellsort() 希尔排序bubblesort() 冒泡排序quicksort() 快速排序selection() 选择排序partition(int lb,int ub,int piv,int *pn,int *pm) 快速排序中使用heapsort() 堆排序merge() 归并排序radixsort() 基数排序void hpsort1(int x,int n,int *count_n,int *count_m) 基数排序中使用四、 调试分析1. 本程序经过多次调试才得以通过执行，从插入排序到基数排序，每一个都经过亲自调试2. 本人觉得本题中最难的是基数排序，在本程序中，我使用递归等方法才做出3. 对本程序的时空分析如下各排序的对比，交换次数如下表：（以下数据为比较次数与数据移动次数之和）少量数据大量数据顺序数据逆序数据插入排序20556965希尔排序4712454258冒泡排序56173245110快速排序1572036367选择排序7214749080堆排序656176839归并排序19941940基数排序402002022由上表可知，在忽略辅助空间的情况考虑，无论运行少量数据和大量数据，归并排序占优，而当数据有序时，插入排序占优，主要因为实现该排序时的算法用了一个辅助数组，大大减少了数据的移动次数，数据完全逆序时，堆排序效率最高。a)从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况 下的时间性能为o(n*n)不如堆排序和归并排序o(n*logn)。而后两者相比较的结果是，在n较大时， 归并排序所需的时间较堆排序省，但它所需的辅助存储量最多。i. 单排序中以直接排序最简单，当序列的记录基本有序或较小时，它是最佳的排序方法。ii. 数排序的时间复杂度较小。因此最适用于n值很大的时候而关键字较小的序列。若关键字也很大，而序列中的大多数记录的最高位关键字均不同，则亦可先按最高位关键字不同将序列分成若干小的子序列，而后进行直接插入排序。iii. 从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为o（n*n）的简单排序也是稳定的，然而，快速排序，堆排序和希尔排序等时间性 能 较好的排序方法都是不稳定的，一般来说，排序过程中的比较是在相临的两个记录关键字间进行的排序方法都是稳定的。由于大多数情况下排序是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。若排序按记录的次关键字进行，则应根据问题所需慎重选择排序方法及其描叙算法。综上所叙，在这些排序方法中没有哪一中是绝对最优的，有的适用于n较大的情况，有的适用于n 较小的情况，因此，在实用时需要根据不同的情况适当选用，甚至可以将多种方法综合起来使用。算法的时空分析和改进设想五、用户使用说明程序运行后,将进入以下主菜单:菜单设计为输入相应的数字进行选择。本人在程序中使用了db10.txt这个文件，只要这个文件存在数据，就可以进行排序，按9可以用来往该文件添加数据，18用来排序分别是1， 插入排序2， 希