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