数据结构程序设计-各种排序算法时间性能的比较

《数据结构程序设计-各种排序算法时间性能的比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号数据结构课程设计设计说明书题目各种排序算法时间性能的比较起止日期：2011年12月12日至2011年12月16日学生姓名班级成绩指导教师(签字)电子与信息工程系2011年12月16日211天津城市建设学院课程设计任务书2011—2012学年第1学期电子与信息工程系软件工程专业班级课程设计名称：数据结构课程设计设计题目：各种排序算法时间性能的比较完成期限：自2011年12月12日至2011年12月16日共1周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严

2、谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。(1)设计并实现上述各种排序算法；(2)产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3)产生随机

3、的初始排列分别调用上述排序算法，并比较时间性能。211四、参考文献1．王红梅．数据结构．清华大学出版社2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社211一、需求分析需要对用户输入的一组数据进行排序，并对7种排序的正逆排序进行分析，并做出时间复杂度的比较，并得出最优的排序方法作为结果。二、问题求解在排序时，开始做出的任何一个排序的的逆排序的时间复杂度都是一个定值不会变，后来经过单步调试，发现是把正排序放在了起之前，所以逆排序排出来的都是已经排好的数据，所以不会变，我通过复制数组，做成了两个数组（最后做成

4、的总程序为多个数组），然后分别对应每个算法做排序。这样就不会在显示后一个算法的排序是前一个算法已经排序好的数组，而是用户输入的原始数组。一下是对于每个排序的分析及所遇见的问题：（排序解释都用正排序说明）1．冒泡排序该排序没有什么打的问题，用两个for循环即可做出排序。排序原理是两两对比大的放前，小的放后。2．插入排序该排序是以第n个数（需排序的数）直接去与数组里已经排序好的数做比较。将其插入比它大的数之前，比它小的数之后。在做该数组的时候我之前以为r[0]的哨兵可以用任意一的变量来代替，从而是数组从r[0]开始计数，结果表明，并不是这样，因为每一次，最小的数都会呗覆

5、盖掉，所以原假设不成立。3．希尔排序：先把数组分成等长的两个数组，用r[i]与r[n/2+i]做比较晓得在前，打的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。4．直接选择排序该排序是现在无序的数组中找最值，然后作为第一个元素，之后就是每次找最值，作为下一个元素，直至最后一个元素，排序完成。5．快速排序定义两个指针，分别只想第一个与最后一个元素，这两个元素做比较，大的放前，小的放后，然后移动指针，进行下一个比较。两次这样比较排序以后，数组变成为了有序数列。该算法采用为递归算法。6．归并排序该排序，也是

6、需要调用递归。先把数组对半分多次，直到每组只有两个数据时，进行对比、排序。然后再两两合并，最后做到整个数组的排序完成7．堆排序先是对堆做比较，左子数小于本数，右子数大于本数，然后不停比较，交换，最后达到整个数组的排序。211三、总体设计每一个排序都给出排序后的数组及本排序的时间复杂度。主程序快速排序冒泡排序插入排序希尔排序直接选择排序归并排序堆排序主程序快速排序冒泡排序插入排序希尔排序直接选择排序归并排序堆排序杂乱数组输出整理排序数组，并作出分析，得到最有方法四、详细设计//冒泡排序211voidZmppx(inta[],intn)//正序排序voidNmppx(i

7、nta[],intn)//逆序排序//插入排序voidZcrpx(intr[],intn)//正序排序voidNcrpx(intr[],intn)//逆序排序//希尔排序voidZxepx(intr[],intn)//正序排序voidNxepx(intr[],intn)//逆序排序//直接选择排序voidZzjxzpx(intr[],intn)//正序排序voidNzjxzpx(intr[],intn)//逆序排序//快速排序voidZkspx(intr[],intleft,intright)//正序排序voidNkspx(intr[],intleft,intr