排序实验报告.doc

排序实验报告.doc数据结构实验报告排序小组成员:张家铭2010416648吴建明2010416603刘仕乾2010416682王战海20104165961实验题目为了更好的学习数据结构,理解排序思想,直观的观察出每一步所进行的操作。进行此实验报告。主要包含直接插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序。2需求分析在现在的任何pc、mac上均可装有c-。输入形式,先用种了函数初始化随机生成函数,然后用随机生成函数生成十个数据。通过选择你想选用的排序方式包括:insertSort(arr,10);//插入排序shellSort(arr,3,10);//希尔排序bubbleSort(arr,1());//冒泡排序QuickSort(arr,1,11);//快速排序selectSort(arr,10);〃选择排序heapsort(arr,10000);//堆排序输出形式,通过调用printarr函数进行输出数据,并在排序Z屮调用此函数了来直观的查看排序的过程。程序附加功能,在排序进行之前设计了开始时间(start=time(NLULL)),在排序结束Z后设计了结束时间(end=time(NULL)),Z后在输出该排序执行的时间(printfC*执行时间为:%d\nM,(end-start));)o直观的看岀该稈序的优劣。PS:执行小量数据体现不出时间损耗,可以设计大量数据看出时间损耗。测试数据,随机生成,数据不定。3概要设计(1)包含的头文件#include<>#inelude<>#include<>用于生成随机函数和计时用木稈序包含的主要函数:voidprintarr(intarr[],intn)voidinsertSort(intarr[],intn)voidshellpass(intarr|J,intd,intn)voidshellSort(intarr[],intbjntn)voidbubbleSort(intarr[],intn)voidQuickSort(intdata[]9intleft,intright)voidselectSort(intarr[],intn)voidshift(intarr[]?inti,intn)voidheapsort(intarrfl,intn)voidmain()各函数Z间的关系如图3・3:〃输出列表函数〃插入排序注意监视硝作用〃希尔排序一趟d为步长〃希尔排序〃冒泡排序〃快速排序重点的排序〃选择排序//建堆i为根节点n为个数〃堆排序〃主函数mainO图,3程序屮各函数之间的关系4详细设计(1)直接插入排序,arr[O]为监视哨的作用。把未排好序的第一个数依次与已排好序的比较,寻找到合适位置插入。详细设计如下:voidinsertSort(intarrnjntn){inti,j;for(i=2;i<=n;i++){arr[O]=arr[i];〃插入排序注意监视哨作用〃安放监视哨j=i・l;while(arr[O]<arr[j]){arr[j+l]=arr|j];j-;}arr[j+l]=arrfOJ;printf("Thatis%dtimesofwhistle%2d:",i-l,arr[0]);//j-很重要〃白己学习观察用;printarr(a