七种排序算法比较与每种排序上机统计时间.doc

数据结构数据结构 课程设计报告课程设计报告 课题 排序算法的比较 学院 信息学院 班级 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 选题要求 选题要求 利用随机函数产生 30000 个随机整数 利用直接插入排序 希尔排序 冒 泡排序 直接选择排序 快速排序 堆排序 归并排序的排序方法进行排序 并统计每一种排序上机所花费的时间 1 21 2 选题的意义及背景 选题的意义及背景 排序是计算机程序设计中的一种重要操作 它的功能是将一个数据元素的 任意序列 重新排列成一个按关键词有序的序列 此实验通过对各种内部排序算法进行比较 能使我们更好的掌握各种排序 的基本思想 掌握各种排序方法的算法实现 掌握各种排序方法的优劣分析及 花费的时间的计算 掌握各种排序方法所适应的不同场合 通过该题目的设计 可以加深理解各种数据结构的逻辑结构 存储结构及相应上运算的实现 进一 步理解与熟练掌握课本中所学的各种数据结构 学会如何把学到的知识用于解 决实际问题 培养我们的动手能力 1 31 3 设计任务书 设计任务书 1 定义结构体 头文件 定义数组范围 大小 2 依次描写七种排序的算法 3 描写产生随机函数的算法 4 描写菜单函数 5 描写主函数 调用七种排序的算法 2 2 设计分析 设计分析 2 12 1 原始资料原始资料 用户输入记录的个数30000个 数据由随机函数生成 2 22 2 输出数据输出数据 产生的随机数分别用冒泡排序 直插排序 希尔排序 选择排序 快速排 序 堆排序 归并排序这些排序方法进行排序 并统计每一种排序上机所花费 的时间 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 定义记录为结构体类型 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 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为实际输入记录数 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 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 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 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 复制第二个有序子表的剩余记录 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 MERGEPASS 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 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 将随机整数存放到数组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 printf 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 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 finish clock time4 double finish start CLOCKS PER SEC printf 快速排序耗时 f seconds n time4 break case 5 start clock select sort s1 12 finish clock time5 double finish start CLOCKS PER SEC printf 直接选择排序耗时 f seconds n time5 break case 6 start clock heap sort s1 finish clock time6 double finish start CLOCKS PER SEC printf 堆排序耗时 f seconds n time6 break case 7 start clock merge sort s1 finish clock time7 double finish start CLOCKS PER SEC printf 二路归并排序耗时 f seconds n time7 break case 0 exit 0 print record s1 while kk 0 MAIN 4 4 测试结果 测试结果 13 1 1 选择直接插入排序 选择直接插入排序 14 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 直接插入排序耗时由图可知 直接插入排序耗时0 8780000 878000秒秒 15 2 2 选择希尔排序 选择希尔排序 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 希尔排序耗时由图可知 希尔排序耗时0 0260000 026000秒秒 16 17 3 3 选择冒泡排序 选择冒泡排序 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 冒泡排序耗时由图可知 冒泡排序耗时3 4560003 456000秒秒 18 19 4 4 选择快速排序 选择快速排序 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 快速排序耗时由图可知 快速排序耗时0 0050000 005000秒秒 20 21 5 5 选择直接选择排序 选择直接选择排序 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 直接选择排序耗时由图可知 直接选择排序耗时1 5280001 528000秒秒 22 23 6 6 选择堆排序 选择堆排序 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 堆排序耗时由图可知 堆排序耗时0 0080000 008000秒秒 24 25 7 7 选择二路归并排序 选择二路归并排序 排序前本有排序前本有3000030000个随机数显示 但数据太多 只截一部分图来表示 个随机数显示 但数据太多 只截一部分图来表示 排序后也一样 应有排序后也一样 应有3000030000个排好顺序的整数显示 但由于数据过多 也只截一个排好顺序的整数显示 但由于数据过多 也只截一 部分图来表示 部分图来表示 由图可知 二路归并排序耗时由图可知 二路归并排序耗时0 0060000 006000秒秒 26 27 5 5 总结与体会总结与体会 总结 总结 由上述比较我们可以清楚地知道 各种排序算法之间的差别是很大的 其中在这几种不同的算法中 快速