测试十 内部排序算法比较

《测试十 内部排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、184实验十内部排序算法比较实验指导书一、实验目的通过内部排序算法实现，帮助学生熟练掌握各种排序算法的基本技术。通过各种排序算法在数据随机分布、正序和逆序情况下，数据比较次数和数据元素移动次数，对不同排序算法的时间复杂度获得直观的感受。二、实验内容实现6中常用内部排序算法：直接插入排序希尔派序冒泡排序快速排序简单选择排序堆排序对每种排序方法，记录其数据比较次数和数据移动次数。要求待排序数据不少于100，数据分布在一个较大的范围内，若1000。待排序序列考虑三种数据分布：数据序列随机分布数据序列递增有序数据

2、序列递减有序三、实验原理1、随机序列生成随机数可用C语言函数库提供的随机数生成函数random自动升，其格式为：random(<整型常数>)该函数随机产生不大于指定常数的正整数。若连续地产生随机数，有可能出现重复的随机数。如果不希望出现重复的数据，在产生的过程中英滤去重复的数据。2、比较次数和元素移动次数计算算法只考虑元素参与的比较和移动。对于条件表达式，若无元素参与比较，则不对其进行比较计数。没有元素参与的赋值运算，则不对其进行移动计数。（1）比较次数的计算：凡是由元素参与比较运算，比较计数器要加1。（

3、2）数据移动次数的计算：将一个元素的值赋给另一个元素，即表示数据的一次移动。如果有两个元素互相交换值，则表示有3次数据移动。185例：对于直接排序算法，其排序及统计算法如下:voidInsertSort(SqList*L){inti,j,temp;CompareCount=0;MoveCount=0;for(i=2;i<=L->Length;i++)比较计数{CompareCount++;if(L->r[i]r[i-1]){L->r[0]=L->r[i];MoveCount++;for(j=i-1

4、;L->r[0]r[j];j--)移动计数{L->r[j+1]=L->r[j];CompareCount++;MoveCount++;}L->r[j+1]=L->r[0];MoveCount++;}}}四、实现1、排序对象当第一次用各种排序方法进行排序时，采用随机函数random生成的序列。对递增有序序列进行排序时，使用第一次排序的结果作为排序对象对递减有序序列进行排序时，将第一次排序结果的逆序作为排序对象。因为对每一组数要用多种方法进行排序，所以在排序过程中，只能用排序数据的副本进行排序，即用每

5、种方法排序前应将排序数据复制到同类型的顺序表中。2、数据类型定义#defineMAXSIZE120#defineFALSE0#defineTRUE1typedefstruct{intr[MAXSIZE+1];intLength;}SqList;1863、程序功能(1)基本功能:产生随机序列数据排序：插入排序希尔排序冒泡排序快速排序简单选择排序堆排序排序比较结果输出（2）辅助功能菜单选择数据复制希尔一趟插入排序快速一趟排序堆筛选排序数据输出4、程序结构该程序由16个函数组成，其中主函数1个，基本功能函数9个

6、，辅助功能函数6个。函数间的调用关系图1所示。mainnemuSortInitsortCompareShiftOutputSortDataDataCopyShellSortInsertSortBubbleSortQickSortSelectSortHeapSortShellInsertPartitionHeapAdjust图10-1程序结构示意图1874、函数说明（1）主函数main功能：根据菜单选择确定要操作的内容：随机数据排序递增数据排序递减数据排序输出统计数据退出系统（2）菜单选择函数：menu功能

7、：构造功能菜单，并选择下一步要操作的功能。格式：intmenu(void)参数：无参数。返回值：1～5中的一个序号。可供选择的功能如下：1---RandomDatasort2---IncreasingDatasort3---DecreasingDatasort4---CompareshiftDataOutput5---Quit表示退出系统，结束程序的运行（3）排序控制函数：sort功能：协调对各种排序函数的调用，统计比较和移动数据格式：voidsort(SqListL,SqList*L1,inta[][6

8、],intNo)参数：SqListL—顺序表（排序对象数据）SqList*L1—指向顺序表的指针（排序结果数据）inta[][6]—二维数组，存放统计数据，分别为每种排序方法的随机、正序、逆序数据的比较和移动统计数据。intNo—指示为随机、正序、逆序的序号，指明存放统计数据的位置返回值：无（4）排序函数：InsertSort，ShellSort，BubbleSort，QickSort，SelectSort，HeapSort功