内部排序算法比较课程设计报告7种基本排序.docx

合肥学院
计算机科学与技术系
课程设计报告
2017　～ 2０１8 学年第一学期
课程
　 　 　 　数据结构与算法
课程设计名称
内部排序算法比较
学生姓名
操彦
学号
１50４0120２7
专业班级
计算机科学与技术系１5级 ２ 班
指导教师
201７ 　年　 ９ 月
ﻬ１、问题分析和任务定义
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。待排序表的表长不少于１00，为方便起见，我们令表长等于10０,用5组随机的数据排序的结果作比较.
数据结构的选择和概要设计
一。可能排序表的抽象数据类型定义:
ＡDT　 OｒdeｒablｅＬｉsｔ{
数据对象:D＝｛｜∈IntｅgｅrSｅt,i＝１，2，……，ｎ，n≥0｝
数据关系：R1＝｛〈,｜，∈D，i=2，……ｎ｝
基本操作:
ＩnｉｔLｉst（n）
操作结果:构造一个长度为n，元素值依次为1,2,……，ｎ的有序表。
ＲａndｏｍiｚｅList(d，iｓIｎveｒseOｒｄeｒ)
操作结果：首先根据isＩnveｒseOrｄｅr为Tｒue或False，将表置为逆序或正序，然后将表进行ｄ（0≤ｄ≤8）级随机打乱。d为0时表不打乱,d越大，打乱程度越高.
ＲecallLisｔ()
操作结果：恢复最后一次用RａnｄomｉzeＬist随机大乱的可排序表.
ListLeｎgth（）
操作结果：返回可排序的长度．
LiｓtEｍｐty（）
操作结果：若可排序表为空表，则返回Ｔｒｕｅ，否则返回Ｆａlｓe。
BubbｌeSｏｒt(＆ｃ，＆s）
操作结果：进行冒泡排序，返回关键字比较次数c和移动次数s。
ＩnsertSoｒt（&c，＆s）
操作结果：进行插入排序,返回关键字比较次数c和移动次数s。
SeｌectSort（&c，＆s）
操作结果：进行选择排序,返回关键字比较次数c和移动次数s.
QuiｃｋSｏrｔ（&c,&s)
操作结果：进行快速排序,返回关键字比较次数c和移动次数s。
ＳhellＳoｒt(＆c,＆s）
操作结果：进行希尔排序,返回关键字比较次数c和移动次数s。
ＨeaｐSｏrｔ(＆c，&s）
操作结果：进行堆排序，返回关键字比较次数c和移动次数s．
ＬistTraveres（viｓit（）)
操作结果：依次对L中的每个元素调用函数vｉsit(）.
｝ＡDＴ ＯrdｅrableList
二．概要设计：
１．冒泡排序：
冒泡排序的基本概念是:依次比较相邻的两个数,将小数放在前面，大数放在后面。即在第一趟:首先比较第1个和第2个数，将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前，大数放后,如此继续，直至比较最后两个数，将小数放前,大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第３个数的交换，使得第1个数不再小于第２个数），将小数放前，大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的)，第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数）.如此下去，重复以上过程,直至最终完成排序.
２．直接插入排序:
直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已牌号序的有序表中，从而得到一个新的、记录数增１的有序表.
简单选择排序：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环。
希尔排序:
希尔排序又称“缩小增量排序”，它也是一种属插入排序类的方法,但在时间效率上较前述集中排序方法有较大的改进。它的基本思想是：先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序.
堆排序：
由二叉堆的定义可知,堆顶元素（即二叉堆的根节点）一定为堆中的最大值或最小值，因此如果我们输出堆顶元素后，将剩余的元素再调整为二叉堆,继而再次输出堆顶元素，再将剩余的元素调整为二叉堆，反复执行该过程，这样便可输出一个有序序列，这个过程我们就叫做堆排序。
归并排序：
-路归并排序,即将含有n个元素的序列看成是ｎ个有序的子序列，每个子序列的长度为1，而后两两合并,得