文档介绍：排序算法比较课程设计说明书设计名称:数据结构课程设计题目:排序算法比较学生姓名:专业:计算机科学与技术班级:11级一班学号:指导教师:李娅日期:2013年3月20日1课程设计任务书计算机科学与技术专业11年级班一、设计题目各种算法排序比较二、主要内容利用随机函数产生N个随机整数(N<10000),对这些数进行多种方法排序。三、要求1)至少采用4种方法实现上述问题求解(可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序),并把排序后的结果保存在不同的文件里。2)给出该排序算法对数据的比较次数和移动次数并统计每一种排序方法的性能(以运行程序所花费的时间为准进行对比),找出其中两种较快的方法。四、进度安排1)资料阅读查找、系统分析,概要设计;)系统详细设计、功能设计;)算法实现、编程调试;时间安排1天4)资料整理、课程设计说明书编写。时间安排1天五、完成后应上交的材料给出系统的概要设计、详细设计;完成核心算法的实现;完成规范化的课程设计说明书的编写。课程设计的总结报告,还应包括以下内容:1(1)课程设计中遇到的主要问题和解决方法;(2)创新和得意之处;(3)课程设计存在的不足,需进一步改进的设想;(4)课程设计的感想和心得体会。以上内容均填写在《课程设计说明书》上,要求干净整洁,符合课程设计的要求和规范。六、总评成绩1指导教师签名日期年月日系主任审核日期年月日1目录排序算法比较一、需求析..................................2二、程序的主要能............................2三、程序运行台..............................3四、算法及时间复度..........................3五、测试结果................................5六、程序源代码..............................6七、感想体会与总结.........................13-11-排序算法比较一、主要内容:利用随机函数产生N个随机整数(N<10000),对这些数进行多种方法排序。具体要求:1)至少采用4种方法实现上述问题求解(可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序),并把排序后的结果保存在不同的文件里。2)给出该排序算法对数据的比较次数和移动次数并统计每一种排序方法的性能(以运行程序所花费的时间为准进行对比),找出其中两种较快的方法。二、、比较次数bj、以及排序所用的时间。三、程序运行平台-21-VisualC++、算法及时间复杂度(一)各个排序是算法思想:(1)直接插入排序:将一个记录插入到已排好的有序表中,从而得到一个新的,记录数增加1的有序表。(2)折半插入排序:插入排序的基本插入是在一个有序表中进行查找和插入,这个查找可利用折半查找来实现,即为折半插入排序。(3)起泡排序:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字。依此类推,直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序,其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序,对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。(4)快速排序:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序。(5)选择排序:通过N-I次关键字间的比较,从N-I+1个记录中选出关键字最小的记录,并和第I(1<=I<=N)个记录交换。(二)时间复杂度分析-31-最差时间时间复杂度是否稳定,排序算法22插入排序O(n)O(n)稳定22冒泡排序O(n)O(n)稳定2快速排序O(n)O(n*logn)不稳定222选择排序O(n)O(n)稳定10000个数据的时间比较:、测试结果1、首先选择需要排序的数字个数,比如输入n=100-41-2、再选择用哪种方法进行排序,比如输入方法13、各种方法排序显示已排序方法的信息5六、程序源代码/**********************************************************************************************第二题:排序算法