数据结构专业课程设计十种排序算法比较

合肥学院

计算机科学与技术系

课程设计报告

2014 ～2015 学年第 学期

课学学专指

业导

班教生

姓

程 数据结构与算法

内部排序算法比较

名 号 级 师

课程设计名称

2015 年 1 月

【课题22、】内部排序算法比较 一、问题分析和任务定义

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 根据对本设计任务要求的理解和分析，按以下两点问题进行分析：

题目要求对十种排序算法进行比较，比较的主要内容是关键字的比较次数和移动次数，其中待排序数用。

二、数据结构的选择和概要设计

为了实现十种排序算法，产生的随机数用顺序表存储比较方便。顺序表数据类型（存储结构）描述如下：

typedef int KeyType; struct rec {

KeyType key; };

typedef rec sqlist[N];

：

(1) void gensort(int b[],int n)起泡排序 (2) void insertsort(sqlist b,int n)插入排序 (3) void so(sqlist num,int n)折半插入排序 (4) void shellsort(sqlist b,int n)希尔排序 (5) void gentsort(int b[],int n)选择排序 (6) void output(sqlist b,int n)快速排序 (7) void sort3(sqlist nu,int n) //2-路插入排序 (8) void Merge(sqlist a, sqlist b, int low, int mid, int high)二路归并排序

(9) void MergePass(sqlist a, sqlist b, int n, int lenth)一趟归并排序

(10) void MergeSort(sqlist a, int n) //进行二路归并

(11) void sift(sqlist r,int s,int m) 堆排序 (12) void init(int a[])//随机生成N个整数

三、详细设计和编码

在整个课程设计中，要求实现要求的功能，必须要有主函数，并通过主函数调用各功能子模块，以上展示各个模块的功能，以下将分析主函数和各个模块中的具体算法和实现。