数据结构算法课程设计-排序算法的实现.doc

河南工程学院《数据结构与算法》课程设计成果报告排序算法的实现学生学号:学生姓名:学院:计算机学院专业班级:软件工程1341专业课程:《数据结构与算法》指导教师:2014年12月29日题目排序算法的实现考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:年月日目录1课程设计目标与任务 12分析与设计 73程序清单 84测试 135总结 14参考文献 。该实践教学是软件设计的综合训练,包括问题分析,总体结构设计用户界面设计,程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼:,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法;,验证自己设计的算法的正确性,学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改;,分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平;,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来,获得算法的直观感受。,完成各种排序的实现,对输入的一组数字实现不同的排序方法,并把排序结果进行保存。,产生20000个随机数。、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序等算法进行编写。,并保存其结果。:产生20000个随机数,并通过各种排序方法对它们进行排序。:插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小,插到前面已经排好的文件中的适当位置,直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。直接插入排序具体算法描述如下:(1)从第一个元素开始,该元素可以认为已经被排序(2)取出下一个元素,在已经排序的元素序列中从后向前扫描(3)如果该元素(已排序)大于新元素,将该元素移到下一位置(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置(5)将新元素插入到下一位置中(6)重复步骤。:折半插入排序是对直接插入排序的简单改进,对于直接插入排序而言,当第i-1趟需要将第i个元素插入前面的0~i-1个元素序列中时,总是需要从i-1个元素开始,逐个比较每个元素,直到找到它的位置。这显然没有利用前面0~i-1个元素已经有序这个特点,而折半插入排序则改进了这一点。对于折半插入排序而言,当需要插入第i个元素时,它不会逐个进行比较每个元素,而是:(1)计算0~i-1索引的中间点,也就是用i索引处的元素和(0+i-1)/2索引处的元素进行比较,如果i索引处的元素值大,就直接在(0+i-1)/2~i-1半个范围内进行搜索;反之在0~(0+i-1)/2半个范围内搜索,这就是所谓的折半;(2)在半个范围内搜索时,按照(1)的方法不断地进行折半搜索,这样就可以将搜索范围缩小到1/2、1/4、1/8…,从而快速的确定插入位置。: 希尔(Shell)排序的基本思想是:先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取得第二个增量d2<d1重复上述的分组和排序,直至所取的增量di=1,即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。    一般取d1=n/2,di+1=di/2。如果结果为偶数,则加1,保证di为奇数。:冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数