欢迎来到天天文库
浏览记录
ID:21782421
大小:2.43 MB
页数:35页
时间:2018-10-24
《内部排序算法的实现和比较》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、WORD资料下载可编辑实验四:内部排序算法的实现与比较一、问题描述1.实验题目:在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。2.基本要求:(1)对常用的内部排序算法进行比较:直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。(2利用随机函数产生N(N=30000)个随机整数,作为输入数据作比较;比较的指标为关键字参加的比较次数和关键字的移动次数(关键字交换记为3次移动)。(3)对结果作出简要分析。3.测试数据:随机函
2、数产生。二、需求分析1.程序所能达到的基本可能:通过随机数据产生N个随机数,作为输入数据作比较;对常用的内部排序算法:直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较:比较的指标为关键字参加的比较次数和关键字的移动次数(关键字交换记为3次移动)。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数,并按从小到大排列。2.输入的形式及输入值范围:随机函数产生的N(N=30000)个随机整数。3.输出的形式:输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。4.测试数据要求:随机函数产生的N(
3、N=30000)个随机整数。三、概要设计1.所用到得数据结构及其ADT为了实现上述功能,应以一维数组表示集合数据类型。ints[N];intcompare[6]={0},move[6]={0},D[N]={0},RS[N]={0};基本操作:数组赋值:for(i=1;i4、RS[],intn)//冒泡排序voidInsertSort(intRS[],intn)//直接插入排序intQuickSort(intRS[],intlow,inthigh)//快速排序voidQuickSortprint(intRS[],intn)//输出快速排序后的结果voidShellsert(intRS[],intm,intn)//一趟希尔排序,按间隔m划分子序列voidShellsort(intRS[],intn)//希尔排序voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列5、voidMSort(intRS[],intlow,inthigh)//归并排序2.主程序流程及其模块调用关系技术资料专业分享WORD资料下载可编辑voidSelectSort(intRS[],intn)//直接选择排序模块技术资料专业分享WORD资料下载可编辑voidBubbleSort(intRS[],intn)//冒泡排序模块技术资料专业分享WORD资料下载可编辑voidInsertSort(intRS[],intn)//直接插入排序模块技术资料专业分享WORD资料下载可编辑intQuickSort(intRS[],intlow,inthigh)/6、/快速排序模块技术资料专业分享WORD资料下载可编辑voidShellsert(intRS[],intm,intn)//一趟希尔排序,按间隔m划分子序列技术资料专业分享WORD资料下载可编辑voidShellsort(intRS[],intn)//希尔排序模块技术资料专业分享WORD资料下载可编辑voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列技术资料专业分享WORD资料下载可编辑模块调用四、详细设计1.实现每个操作的伪码,重点语句加注释1)voidcopys(intS[],intRS7、[],intn)//数组复制{inti;for(i=1;i8、i=1;i<=n;i++)printf("%dt",RS[i]);printf("");
4、RS[],intn)//冒泡排序voidInsertSort(intRS[],intn)//直接插入排序intQuickSort(intRS[],intlow,inthigh)//快速排序voidQuickSortprint(intRS[],intn)//输出快速排序后的结果voidShellsert(intRS[],intm,intn)//一趟希尔排序,按间隔m划分子序列voidShellsort(intRS[],intn)//希尔排序voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列
5、voidMSort(intRS[],intlow,inthigh)//归并排序2.主程序流程及其模块调用关系技术资料专业分享WORD资料下载可编辑voidSelectSort(intRS[],intn)//直接选择排序模块技术资料专业分享WORD资料下载可编辑voidBubbleSort(intRS[],intn)//冒泡排序模块技术资料专业分享WORD资料下载可编辑voidInsertSort(intRS[],intn)//直接插入排序模块技术资料专业分享WORD资料下载可编辑intQuickSort(intRS[],intlow,inthigh)/
6、/快速排序模块技术资料专业分享WORD资料下载可编辑voidShellsert(intRS[],intm,intn)//一趟希尔排序,按间隔m划分子序列技术资料专业分享WORD资料下载可编辑voidShellsort(intRS[],intn)//希尔排序模块技术资料专业分享WORD资料下载可编辑voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列技术资料专业分享WORD资料下载可编辑模块调用四、详细设计1.实现每个操作的伪码,重点语句加注释1)voidcopys(intS[],intRS
7、[],intn)//数组复制{inti;for(i=1;i8、i=1;i<=n;i++)printf("%dt",RS[i]);printf("");
8、i=1;i<=n;i++)printf("%dt",RS[i]);printf("");
此文档下载收益归作者所有