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

《数据结构与算法》课程设计成果报告排序算法实现学生学号:学生姓名:学院:计算机学院专业班级:软件工程1341专业课程:《数据结构与算法》指导教师:2014年12月29日题目排序算法实现考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:年月日目录1课程设计目标与任务 12分析与设计 73程序清单 135总结 14参考文献 。该实践教学是软件设计的综合训练,包括问题分析,总体结构设计用户界面设计,程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼。,以便在程序设计中调用,要求设计程序,产生20000个随机数,完成下面功能:(1)对这些数分别进行直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序,堆排序,2路-归并排序等排序,并把排序结果进行保存。(2)最好能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;(3)给出若干例程,演示通过调用自己所写程序来实现相关问题的要求。,独立进行设计,不能随意更改。若确因条件所限,必须要改变课题要求时,应在征得指导教师同意的前提下进行。学生应制定实****工作计划,认真完成实****的各个环节,并在老师的指导下认真组织实****工作,撰写实****报告,做好实****总结。:设有一组关键字{K1,K2….Kn},排序开始便认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为2的有序序列,使之成为表长为3的有序序列,依次类推,最后Kn插入到上述表长为n-1的有序序列,得到一个表长为n的有序序列。:在将一个新元素插入已排好序的数组的过程中,寻找插入点时,将待插入区域的首元素设置为a[low],末元素设置为a[high],则轮比较时将待插入元素与a[m],其中m=(low+high)/2相比较,如果比参考元素小,则选择a[low]到a[m-1]为新的插入区域(即high=m-1),否则选择a[m+1]到a[high]为新的插入区域(即low=m+1),如此直至low<=high不成立,即将此位置之后所有元素后移一位,并将新元素插入a[high+1]。:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2,d2<d1,再将到d2作为增量继续分组,再进行直接插入排序,依次向下取值,直到完成排序。:比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。:快速排序的实现基于分治法,具体分为三个步骤。假设待排序的序列为L[m..n]。序列L[m..n]被划分成两个可能为空的子序列L[m..pivot-1]和L[pivot+1..n],使L[m..pivot-1]的每个元素均小于或等于L[pivot],同时L[pivot+1..n]的每个元素均大于L[pivot]。其中L[pivot]称为这一趟分割中的主元(也称为枢轴、支点)。通过递归调用快速排序,对子序列L[m..pivot-1]和L[pivot+1..r]排序。由于两个子序列是就地排序的,所以对它们的合并不需要操作,整个序列L[m..n]已排好序。:序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(R,Ri+1,…,Rn中找出排序码最小的记录,与第i个记录交换。执行n-1趟后就完成了记录序列的排序。