《（时间管理）七种排序算法的比较及每种排序的上机统计时间》由会员分享，可在线阅读，更多相关《（时间管理）七种排序算法的比较及每种排序的上机统计时间（29页珍藏版）》请在金锄头文库上搜索。
1、 数据结构数据结构 课程设计报告课程设计报告 课题 排序算法的比较 学院 信息学院 班级 2011 级电子信息工程 1 班 小组成员 韦志东 组长 20111601310027 夏琪 20111601310028 完成时间 2014 01 08 教师 周铁 1 目录 1 课程分析 2 1 1 选题 2 1 2 选题的意义及背景 2 1 3 设计任务 书 2 2 设计分析 2 2 1 原始数据 2 2 2 输出数据 2 2 3 程序流程图 3 3 程序源代码及注释 3 4 测试结果 12 5 总结 26 6 参考文献 27 7 小组人员分工 27 2 1 1 课程分析 课程分析 1 11 1 选
2、题要求 选题要求 利用随机函数产生 30000 个随机整数 利用直接插入排序 希尔排序 冒 泡排序 直接选择排序 快速排序 堆排序 归并排序的排序方法进行排序 并统计每一种排序上机所花费的时间 1 21 2 选题的意义及背景 选题的意义及背景 排序是计算机程序设计中的一种重要操作 它的功能是将一个数据元素的 任意序列 重新排列成一个按关键词有序的序列 此实验通过对各种内部排序算法进行比较 能使我们更好的掌握各种排序 的基本思想 掌握各种排序方法的算法实现 掌握各种排序方法的优劣分析及 花费的时间的计算 掌握各种排序方法所适应的不同场合 通过该题目的设计 可以加深理解各种数据结构的逻辑结构 存储
3、结构及相应上运算的实现 进一 步理解和熟练掌握课本中所学的各种数据结构 学会如何把学到的知识用于解 决实际问题 培养我们的动手能力 1 31 3 设计任务书 设计任务书 1 定义结构体 头文件 定义数组范围 大小 2 依次描写七种排序的算法 3 描写产生随机函数的算法 4 描写菜单函数 5 描写主函数 调用七种排序的算法 2 2 设计分析 设计分析 2 12 1 原始资料原始资料 用户输入记录的个数30000个 数据由随机函数生成 2 22 2 输出数据输出数据 产生的随机数分别用冒泡排序 直插排序 希尔排序 选择排序 快速排 序 堆排序 归并排序这些排序方法进行排序 并统计每一种排序上机所花
4、费 的时间 3 2 32 3 程序流程图程序流程图 3 3 程序源代码及其注释 程序源代码及其注释 include stdio h include stdlib h include math h include include define MAX 60000 记录数组的个数 主程序 产生 1 组随机数 将随机数保存在数组中 直接 插入 排序 冒泡 排序直接 选择 排序 二路 归并 排序堆排 序 快速 排序 Shell 排序 输出排序上机所花费的时间 4 define NUM 30000 实际输入数组的个数 typedef int datatype typedef struct 定义记录为结构
5、体类型 int key 记录的关键词域 datatype other 记录的其它域 rectype rectype s1 s MAX s MAX 存放原始随机数 s1取出原始数据后进行排序 直接插入排序算法如下 void insert sort rectype r 对数组r按递增顺序进行插入排序算法 int i j n NUM NUM为实际输入的记录数 是一个常量 for i 1 i n i i NUM 条件很重要 NUM为实际记录数 r 0 r i r 0 为监视哨 j i 1 依次插入记录r 1 r NUM while r 0 key0 jump jump 2 取步长d i 1 d i 2
6、 do change 0 设置交换标志 change 0表示未交换 for i 1 ir m key 记录交换 temp r m key r m key r i key r i key temp change 1 change 1表示有交换 if for 本趟排序完成 while change 1 当change 0时终止本趟排序 while 当增量jump 1且change 0时终止算法 SHELLSORT 冒泡排序算法如下 void bubble sort rectype r 从下往上扫描的冒泡排序 int i j noswap 0 n NUM noswap为交换标志 NUM为实际输入记录
7、数 rectype temp for i 1 i i j 从下往上扫描 if r j key temp key 从右往左扫描 查找第一个关键词小于temp的记录 if i j r i r j 交换r i 和r j while r i key temp key 从左往右扫描 查找第一个关键词大于temp的记录 if i j r j r i 交换r i 和r j while i j i j z则一次划分结束 基准记录达到其最终位置 r i temp 最后将基准记录temp定位 return i PARTITION void quick sort rectype r int hs int ht 对r
8、 hs 到r ht 进行快速排序 int i if hs ht 只有一个记录或无记录时无需排序 i partition r hs ht 对r hs 到r ht 进行一次划分 quick sort r hs i 1 递归处理左区间 quick sort r i 1 ht 递归处理右区间 QUICK SORT 直接选择排序算法如下 void select sort rectype r rectype temp int i j k n NUM NUM为实际输入记录数 for i 1 i n i 做n 1趟选择排序 k i for j i 1 j n j 在当前无序区中选择关键词最小的记录r k if
9、 r j key r k key k j if k i temp r i 交换记录r i 和r k 7 r i r k r k temp for SELECT SORT 堆排序算法如下 void shift rectype r int i int m 堆的筛选算法 在数组中r i 到r m 中 调整堆 r i int j rectype temp temp r i j 2 i while j m j m r 2 i 是r i 的左孩子 if j m j指向r i 的左右孩子中关键词较大者 if temp key0 i 建立初始堆 shift r i n 8 for i n i 1 i 进行n
10、1趟筛选 交换 调整 完成堆排序 temp r 1 将堆顶元素r 1 与最后一个元素交换位置 r 1 r i r i temp shift r 1 i 1 将数组元素r 1 到r i 1 重新调整成为一个新堆 FOR HEAP SORT 二路归并排序算法如下 void merge rectype a rectype r int low int mid int high int i j k i low j mid 1 k low while i mid else r k a j while i mid r k a i 复制第一个有序子表的剩余记录 while j high r k a j 复制第
11、二个有序子表的剩余记录 MERGE void merge pass rectype r rectype r1 int length int i 1 j n NUM while i 2 length 1 n 归并若干长度为2 length的两个相邻有序子表 merge r r1 i i length 1 i 2 length 1 i i 2 length i指向下一对有序子表的起点 if i length 1 n merge r r1 i i length 1 n 处理表长不足2 length的部分 else for j i j n j r1 j r j 将最后一个子表复制到r1中 9 MERG
12、EPASS void merge sort rectype r int length rectype r1 MAX length 1 归并长度从1开始 while length NUM merge pass r r1 length 一趟归并 结果存放在r1中 length 2 length 归并后有序表的长度加倍 merge pass r1 r length 再次归并 结果存放在r中 length 2 length 再次将归并后有序表的长度加倍 MERGE SORT void creat randnum int a 产生给定个数和范围的随机整数函数 int i int range 30000
13、srand time NULL for i 1 i NUM i a i rand 调用rand生成随机整数 printf n n t t t排序前的原始随机整数为 n n t for i 1 i NUM i printf 6d a i 输出随机整数 if i 10 0 printf n t printf n CREAT RANDNUM void create 产生NUM个随机整数并保存到记录数组s中 int b MAX int range 30000 i creat randnum b 调用随机整数生成函数 结果存放在数组b中 for i 1 i NUM i 10 s i key b i 将随
14、机整数存放到数组s中 s1 s s1指向s 以便保存原始数据 CREAT void print record rectype r 记录数组的输出函数 int i printf n t t t排序后的有序随机整数 n n t for i 1 i NUM i printf 6d r i key if i 10 0 printf n n t getchar getchar PRINTRECORD int menu select 主菜单选择模块 char c int kk system cls 清屏函数 printf 内排序算法的比较 主控模块 n n printf t t t1 直接插入排序 n p
15、rintf t t t2 希尔排序 n printf t t t3 冒泡排序 n printf t t t4 快速排序 n printf t t t5 直接选择排序 n printf t t t6 堆排序 n printf t t t7 二路归并排序 n printf t t t0 退出 n do printf n t t t请按数位0 7键选择功能 c getchar kk c 48 while kk7 return kk MENU SELECT 11 main 算法比较 主程序模块 double time1 time2 time3 time4 time5 time6 time7 clock
16、 t start finish int kk do kk menu select 进入主菜单选择模块 if kk 0 create 建立记录数组 switch kk case 1 start clock insert sort s1 finish clock time1 double finish start CLOCKS PER SEC printf 直接插入排序耗时 f seconds n time1 break case 2 start clock shell sort s1 finish clock time2 double finish start CLOCKS PER SEC printf 希尔排序耗时 f seconds n time2 break case 3 start clock bubble sort s1 finish clock time3 double finish start CLOCKS PER SEC printf 冒泡排序耗时 f seconds n time3 break case 4 start clock quick sort s1 1 NUM
