排序实验报告

计算机科学与技 指导教师 起止时间

任务：n个随机整数（0以上（以上机运行程序所耗费的时间为准进行对比12数据数量能够预先拟定（0以上 int KeyType; intInfoType; struct{ key; //}RedType; struct{ * ////r[0]intlength // SqList（一）60.（二）由课题规定可将程序划分为下列几个模块（即实现程序功效所需的函数创立排序表函数LQSort（三）QSortQSort(for循环实现重复选择。其循环构造以下：for{longstart,end;{case printf("%dms\n",end-start);{}fprintf(fp,"%d",L.r[i]);case printf("%dms\n",end-start);fp=fopen("D:.txt","w");{}fprintf(fp,"%d",L.r[i]);case3: printf("%dms\n",end-start);fp=fopen("D:起泡排 {}fprintf(fp,"%d",L.r[i]);case4: QSort(L,0,L.length);printf("%dms\n",end-start);fp=fopen("D:.txt","w");{printf("打开文献失败}fprintf(fp,"%d",L.r[i]);case5: printf("%dms\n",end-start);fp=fopen("D:.txt","w");{}fprintf(fp,"%d",L.r[i]);case0:printf("\t退 出！\n");return;}}（四）（五）1、r批示线性表的基址，length批示线性表的现在长度，将随机生成的数30000代码描述：StatusInitList_Sq(SqList //FILEL.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType));if(!L.r) exit(OVERFLOW);//存储分派失败 //表长度为30001for(inti=1;i<=L.length;i++){}fprintf(fp,"%d",L.r[i]);return是L.r[i].key<L.r[i-1].key 否 是j=i-代码描述：voidInsertsort(SqList&L)//L for(int (LT(L.r[i].key,L.r[i-1].key))L.r[i]{L.r[0]=L.r[i]; for(intj=i-1;LT(L.r[0].key,L.r[j].key);j--)//位置j批示了第一种key≤L.r[i].key的元素 O（n2）算法原理：12、组数逐次减小；3、组数=1，结束。i<L.length L.r[i].key<L.r[i-dk].key 是L.r[0]=L.rj=i-(j>0)&&(LT(L.r[0].key,L.r[j].key 是j-j-L.r[j+dk]=L.r[0]L.r[j+dk]=L.r代码描述：voidShellInsert(SqList&L,int{//Shell排序，dk为步长inti;{if(LT(L.r[i].key,L.r[i-dk].key{L.r[0]=L.rintfor(j=i-dk;(j>0)&&(LT(L.r[0].key,L.r[j].key));j-L.r[j+dk]=L.rL.r[j+dk]=L.r}}}4、代码描述：voidShellSort(SqList dlta[],int//Shell排序，dlta[]为增量序列，tintk;}//L.r[j]j=n-代码描述：voidBubble_sort(SqList{RedTypex;intn; (inti=1;i<n;intflag=0;进入循环，清标志for(intj=n-1;j>=i;j--){ //L.r[j]←→L.r[j+1]}if(flag==0) //}}ri前的统计排序码<=ri.keyri后的排序码，该过程为一趟快速排序。这样就拟定了Ri在序列中的最后位置，同时将序列分成两个子序列。Low<highLow<high 是low<high&& 是--L.r[low]low<high&& 否是L.r[low]L.r[low]return代码描述：intPartition(SqList&L,intlow,int /*r[low…high]的统计，使枢轴统计到位，并返回其位置。返回时，在枢轴之前的 intpivotkey; //pivotkey变量while(low<high){//从表的两端交替地向中间扫描RedTypeRedTypewhile(low<high&&L.r[high].key>=pivotkey)--high;while(low<high&&L.r[low].key<=pivotkey) } return 7、流程图 开pivotloc=Partition(L,low,high)QSort(L,low,pivotloc-1)QSort(L,pivotloc+1,high) intlow,inthigh){//对次序表L中的子序列r[iflow<high){//长度 pivotloc=PartitionL,low,highr[QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high);//1}}8、1R[1]~R[n]中选用最小值,R[1]交换2R[2]~R[n]中选用最小值,R[2]交换第 第n-1R[n－1]~R[n]中选用最小值,R[n－1]交换i<L.length 是否是i<L.length 是否是否是代码描述：voidSelectSort(SqList对次序表进行简朴选择排序RedTypex;for(i