内部排序算法的实现与比较

《内部排序算法的实现与比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四：内部排序算法的实现与比较一、问题描述1．实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。2．基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。（2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。（3)对结果作出简要分析

2、。3．测试数据：随机函数产生。二、需求分析1．程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。2．输入的形式及输入值范围：随机函数产生的N（N=30000）个随机整数。3．输出的形式：输出各种排序算法的关键字参加的比较次数和关键字

3、的移动次数。并按从小到大排列。4．测试数据要求：随机函数产生的N（N=30000）个随机整数。三、概要设计1.所用到得数据结构及其ADT为了实现上述功能，应以一维数组表示集合数据类型。ints[N];intcompare[6]={0},move[6]={0},D[N]={0},RS[N]={0};基本操作：数组赋值：for(i=1;i

4、,voidSelectSort(intRS[],intn)//直接选择排序voidBubbleSort(intRS[],intn)//冒泡排序voidInsertSort(intRS[],intn)//直接插入排序intQuickSort(intRS[],intlow,inthigh)//快速排序voidQuickSortprint(intRS[],intn)//输出快速排序后的结果voidShellsert(intRS[],intm,intn)//一趟希尔排序，按间隔m划分子序列voidShellsort(

5、intRS[],intn)//希尔排序voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列voidMSort(intRS[],intlow,inthigh)//归并排序2.主程序流程及其模块调用关系voidSelectSort(intRS[],intn)//直接选择排序模块voidBubbleSort(intRS[],intn)//冒泡排序模块voidInsertSort(intRS[],intn)//直接插入排序模块intQuickSort(i

6、ntRS[],intlow,inthigh)//快速排序模块voidShellsert(intRS[],intm,intn)//一趟希尔排序，按间隔m划分子序列voidShellsort(intRS[],intn)//希尔排序模块voidMerge(intRS[],intlow,intmid,inthigh)//将两个有序序列归并为一个有序序列模块调用四、详细设计1.实现每个操作的伪码，重点语句加注释1）voidcopys(intS[],intRS[],intn)//数组复制{inti;for(i=1;i

7、;i++)RS[i]=S[i];}2）直接选择排序voidSelectSort(intRS[],intn)//直接选择排序{inti,j,k;for(i=1;i

8、S[i]);printf("");printf("关键字参加的比较次数：%d,关键字的移动次数：%d",compare[0],move[0]);printf("");}2）冒泡排序voidBubbleSort(intRS[],intn)//冒泡排序{inti,j,flag;for(i=1;i<=n;i++){flag=True;for(j=1;j<=n-i;j++){if(RS[j+1]