合肥学院计算机科学与技术系
课程设计报告
2014～2015学年第学期
课
程
数据结构与算法
课程设计名称学生姓名
内部排序算法比较
学
号
专业班级
指导教师
2015年1月
f【课题22、】内部排序算法比较
一、问题分析和任务定义
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
根据对本设计任务要求的理解和分析，按以下两点问题进行分析：题目要求对十种排序算法进行比较，比较的主要内容是关键字的比较次数和移动次数，其中待排序数用。
二、数据结构的选择和概要设计
为了实现十种排序算法，产生的随机数用顺序表存储比较方便。顺序表数据类型（存储结构）描述如下：typedefi
tKeyTypestructrecKeyTypekeytypedefrecsqlistN2主程序与各模块之间的关系是：1voidge
sorti
tbi
t
起泡排序2voidi
sertsortsqlistbi
t
插入排序3voidsosqlist
umi
t
折半插入排序4voidshellsortsqlistbi
t
希尔排序5voidge
tsorti
tbi
t
选择排序6voidoutputsqlistbi
t
快速排序7voidsort3sqlist
ui
t
2路插入排序8voidMergesqlistasqlistbi
tlowi
tmidi
thigh二路归并排序9voidMergePasssqlistasqlistbi
t
i
tle
th一趟归并排序10voidMergeSortsqlistai
t
进行二路归并11voidsiftsqlistri
tsi
tm堆排序12voidi
iti
ta随机生成N个整数
三、详细设计和编码
在整个课程设计中，要求实现要求的功能，必须要有主函数，并通过主函数调用各功能子模块，以上展示各个模块的功能，以下将分析主函数和各个模块中的具体算法和实现。
1起泡排序函数的实现函数声明：voidge
sorti
tbi
t
起泡排序的基本思想是将第一个记录的关键字和第二个记录的关键字进行
比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键
f字。依次类推，直至第
1个记录和第
个记录的关键字进行比较为止。起泡排序是一种稳定的排序方法，在随机产生数的情况下，总的时间复杂度为O
2。
2选择排序函数的实现函数声明：voidge
tsorti
tbi
t
选择排序法的基本思想是：第i趟排序通过
i次关键码的比较，在
1i1i
1个记录中选取关键码最小的记录，并和第i个记录交换
作为有序序列的第i个记录。选择排序是一种稳定的排序方法，总的时间复杂度是O
2。3插入排序函数的实现
函数声明：voidi
sertsortsqlistbi
t
直接插入排序是一种最简单的排序方法，它的基本操作是将r