- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
几种常见排序算法实现与性能分析数据结构课程设计报告
课程设计(论文)
题 目 名 称 几种常见的排序算法的实现与性能分析
课 程 名 称 数据结构课程设计
学 生 姓 名
学 号
系 、专 业 信息工程系、通信工程
指 导 教 师
2012年 12 月 23 日
摘 要
设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数。运用多种自定义函数,通过在主函数中调用自定义函数,实现其功能,最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数(关键字的交换记为三次移动)。从而直观的判断各内部排序算法性能的优劣性。
关键词:起泡排序;直接排序;简单选择排序;快速排序;希尔排序;堆排序;内部排序;直观;比较次数;移动次数
目录
1 1
2 需求分析 1
3 概要设计 1
3.1抽象数据类型定义 1
3.2模块划分 2
4 详细设计 3
4.1数据类型的定义 3
4.2主要模块的算法描述 3
5 测试分析 8
6 课程设计总结 12
参考文献 12
附录(源程序清单) 13
1 问题描述
设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100,表中数据随机产生,至少用5组不同数据作比较,比较指标有:关键字参加比较次数和关键字的移动次数(关键字交换记为3次移动)。最后输出比较结果。
2 需求分析
(1)用数组S来存放系统随机产生的100个数据,并放到R数组中,数据由程序随机产生,用户只需查看结果。
(2)利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数,然后输出结果,并在每一次统计之后,将times和changes都赋值为0。
(3)在主函数中调用用户自定义函数,输出比较结果。
(4)本程序是对几种内部排序算法的关键字进行性能分析的程序,它分为以下几个部分:a、b、调用函数求比较和移动次数;c、输出结果。
3 概要设计
3.1抽象数据类型定义
排序数据类型定义ADT paixu{
数据对象:D={aij|aij属于{1,2,3…},i,j0}
数据关系:R={ai-1,ai|ai-1,ai∈D,i=2,...,n}
Insertsort();
初始条件:数组已经存在。
基本思想:将一个记录插入到已经排好序的有序列表中,从而得到了一个新的、记录新增1的有序表。
Shellsort();
初始条件:数组已经存在。
基本思想:先取定一个正整数d1n,把全部记录分成d1个组,所有距离为d1倍数的记录放在一组中,在各组内进行插入排序,然后取d2d1重复上述分组和排序工作,直至取di=1,即所有记录放在一个组中排序为止。
Bubblesort();
初始条件:数组已经存在。
基本思想:两两比较待排序记录的键值,并交换不满足顺序要求的那些偶对,直到全部满足顺序要求为止。
QuickSort(int low,int high);
Selectsort();
初始条件:数组已经存在。
基本思想:每次从待排序的记录中选出键值最小(或最大)的记录,顺序放在已排序的记录序列的最后,直到全部排完。对待排序的文件进行n-1趟扫描,第i趟扫描选出剩下的n-i+1个记录,并与第i个记录交换。
Heap();
初始条件:数组已经存在。
基本思想:对一组待排序的的键值,首先是把它们按堆的定义排列成一个序列(称为初建堆),这就找到了最小键值,然后把最小的键值取出,用剩下的键值再重建堆,便得到次小键值,如此反复进行,知道把全部键值排好序为止。
}ADT 排序
3.2模块划分
本程序包括个模块:
(1)主程序模块
void main()
{
初始化;2)子函数模块:实现直接插入排序的抽象数据类型。
实现希尔排序的抽象数据类型。
实现冒泡排序的抽象数据类型。
实现快速排序的抽象数
文档评论(0)