合并排序（分治策略）报告.doc
需积分: 22 136 浏览量
2019-12-26
16:28:55
上传
评论 3
收藏 85KB DOC 举报
实验二：合并排序（分治策略）报告
2017061111 李静娴
1．问题描述
实现对 n 个元素进行排序。
2．实验目的
（1）熟悉分治算法，并学以致用
（2）熟练掌握合并排序算法
3．实验原理
将待排序元素分成大小一致相同的 2 个子集合，分别对 2 个子集合进行排序，最终将
排好序的子集合并成为所要求的排好序的集合。
二分查找算法时间复杂度分析：
合并排序算法对 n 个元素进行排序，在最坏情况下所需的计算时间 T(n)满足
解此递归方程可知 T(n)=O(nlogn)。
4．实验设计
（1）
输入数据格式：程序根据宏定义的数据规模随机生成数组元素，要求都为整型的数
生成方式：在宏定义完数据规模之后，程序中先生成基于当前时间的随机数种子，然后通
过 for 循环语句，每次用随机函数生成一个范围在 0-100 的随机数并将其放入数组中。
数据规模：程序宏定义数据规模 N。
（2）
该程序先是基于当前系统时间生成随机数种子，再根据宏定义的数据规模创建一个相
应大小的整形数组，然后通过 for 循环语句和随机函数 rand()循环生成数据规模个数的元素
并存入创建的数组中。然后调用写好的合并排序函数，将该无序数组排序，并在调用函数
的前后使用 clock()函数记入时间，用于计算合并排序算法的运行时间并输出。
（3）
程序运行的结果有四个，先是输出要排序的数组规模，再输出生成的无序数组，接着
输出合并排序后的数组，最后输出合并排序算法的运行时间。
5．实验结果与分析
资源评论
