实验10：排序子系统

验证性实验10：排序子系统班级：H1001学号：09姓名：陆俊实验日期：2023.12.71．实验目的〔1〕掌握常用排序方法的根本思想。〔2〕通过实验加深理解各种排序算法。〔3〕通过实验掌握各种排序方法的时间复杂度分析。〔4〕了解各种排序方法的优缺点及适用范围。2．实验内容〔1〕编写直接插入排序程序。〔2〕编写希尔排序程序。〔3〕编写冒泡排序程序。〔4〕编写快速排序程序。〔5〕编写选择排序程序。〔6〕编写归并排序程序。〔7〕编写堆排序程序。〔8〕程序执行时，要求能显示每一趟的排序结果。〔9〕设计一个选择式菜单，以菜单方式选择上述排序程序。排序子系统 *************************************************** *1------------更新排序数据* *2------------直接插入排序* *3------------希尔排序* *4------------冒泡排序* *5------------快速排序* *6------------选择排序* *7------------归并排序* *8------------堆排序* *0------------返回* ***************************************************请选择菜单号〔0--8〕：3．实验程序#include<stdio.h>#include<stdlib.h>#include<math.h>#defineL8#defineFALSE0#defineTURE1typedefstruct{ intkey; charotherinfo;}RecType;typedefRecTypeSeqlist[L+1];intnum;SeqlistR;voidInsertsort();voidBubblesort();voidQuickSort(intlow,inthigh);voidShellsort();voidSelectsort();voidMergesort();intPartition(inti,intj);voidHeap();voidmain(){ SeqlistS; inti,k; charch1,ch2,q; printf("\n\t请输入%d个待排序数据〔按【Enter】键分隔〕：\n\t",L); for(i=1;i<=L;i++) { scanf("%d",&S[i].key); getchar(); printf("\t"); } printf("\n\t排序数据已经输入完毕！"); ch1='y'; while(ch1=='y'||ch1=='Y') { printf("\n"); printf("\n\t\t排序子系统"); printf("\n\t\t***************************************************"); printf("\n\t\t*1------------更新排序数据*"); printf("\n\t\t*2------------直接插入排序*"); printf("\n\t\t*3------------希尔排序*"); printf("\n\t\t*4------------冒泡排序*"); printf("\n\t\t*5------------快速排序*"); printf("\n\t\t*6------------选择排序*"); printf("\n\t\t*7------------归并排序*"); printf("\n\t\t*8------------堆排序*"); printf("\n\t\t*0------------返回*"); printf("\n\t\t***************************************************"); printf("\n\t\t请选择菜单号〔0--8〕："); scanf("%c",&ch2); getchar(); for(i=1;i<=L;i++) R[i].key=S[i].key; switch(ch2) { case'1': printf("\n\t请输入%d个待排序数据〔按【Enter】键分隔〕：\n\t",L); for(i=1;i<=L;i++) { scanf("%d",&S[i].key); getchar(); printf("\t"); } printf("\n\t排序数据已经输入完毕！"); break; case'2':Insertsort();break; case'3':Shellsort();break; case'4':Bubblesort();break; case'5':printf("\n\t原始数据为〔按【Enter】键开始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); num=0; QuickSort(1,L); printf("\n\t排序的最终结果是："); for(k=1;k<=L;k++) printf("%5d",R[k].key); printf("\n");break; case'6':Selectsort();break; case'7':Mergesort();break; case'8':Heap();break; case'0':ch1='n';break; default:printf("\n\t输入出错！"); } if(ch2!='0') { if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8') printf("\n\t排序输出完毕！"); printf("\n\n\t按回车键返回。"); q=getchar(); if(q!='\xA') { getchar(); ch1='n'; } } }}voidInsertsort(){ inti,j,k,m=0; printf("\n\t原始数据为〔按【Enter】键开始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); for(i=2;i<=L;i++) { if(R[i].key<R[i-1].key) { R[0]=R[i];j=i-1; while(R[0].key<R[j].key) { R[j+1]=R[j]; j--; } R[j+1]=R[0]; } m++; printf("\t第%d趟排序结果为〔按【Enter】键继续〕：",m); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最终结果是："); for(i=1;i<=L;i++) printf("%5d",R[i].key); printf("\n");}voidShellsort(){ inti,j,gap,x,m=0,k; printf("\n\t原始数据为〔按【Enter】键开始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); gap=L/2; while(gap>0) { for(i=gap+1;i<=L;i++) { j=i-gap; while(j>0) { if(R[j].key>R[j+gap].key) { x=R[j].key;R[j].key=R[j+gap].key; R[j+gap].key=x; j=j-gap; } else j=0; } } gap=gap/2; m++; printf("\t第%d趟排序结果为〔按【Enter】键继续〕：",m); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最终结果是："); for(i=1;i<=L;i++) printf("%5d",R[i].key); printf("\n");}voidBubblesort(){ inti,j,k; intexchange; printf("\n\t原始数据为〔按【Enter】键开始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); for(i=1;i<=L;i++) { exchange=FALSE; for(j=L;j>=i+1;j--) if(R[j].key<R[j-1].key) { R[0].key=R[j].key; R[j].key=R[j-1].key; R[j-1].key=R[0].key; exchange=TURE; } if(exchange) { printf("\t第%d趟排序结果为〔按【Enter】键继续〕：",i); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } } printf("\n\t排序的最终结果是："); for(i=1;i<=L;i++) printf("%5d",R[i].key); printf("\n");}intPartition(inti,intj){ RecTypepirot=R[i]; while(i<j) { while(i<j&&R[j].key>=pirot.key) j--; if(i<j) R[i++]=R[j]; while(i<j&&R[j].key<=pirot.key) i++; if(i<j) R[j--]=R[i]; } R[i]=pirot; returni;}voidQuickSort(intlow,inthigh){ intpirotpos,k; if(low<high) { pirotpos=Partition(low,high); num++; printf("\t第%d趟排序结果为〔按【Enter】键继续〕：",num); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); QuickSort(low,pirotpos-1); QuickSort(pirotpos+1,high); }}voidSelectsort(){ inti,j,k,h; printf("\n\t原始数据为〔按【Enter】键开始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); for(i=1;i<=L;i++) { h=i; for(j=i+1;j<=L;j++) if(R[j].key<R[h].key) h=j; if(h!=j) { R[0]=R[i]; R[i]=R[h]; R[h]=R[0]; } printf("\t第%d趟排序结果为〔按【Enter】键继续〕：",i); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最终结果是："); for(i=1;i<=L;i++) printf("%5d",R[i].key); printf("\n");}voidMerge(intlow,intmm,inthigh){ inti=low,j=mm+1,p=0; RecType*R1; R1=newRecType[high-low+1]; if(!R1) printf("\n\t内存容量不够！"); while(i<mm&&j<=high) R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++]; while(i<=mm) R1[p++]=R[i++]; while(i<=high) R1[p++]=R[j++]; for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p];}voidMergePass(intlength){ inti; for(i=1;i+2*length-1<=L;i=i+2*length) Merge(i,i+length-1,i+2*length-1); if(i+length-1<L) Merge(i,i+length-1,L);}voidMergesort(){ intlength,k,m=0; printf("\n\t原始数据为〔按【Enter】键开始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); for(length=1;length<L;length*=2) { MergePass(length); m++; printf("\t第%d趟排序结果为〔按【Enter】键继续〕：",m); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最终结果是："); for(k=1;k<=L;k++) printf("%5d",R[k].key); printf("\n");}voidCreateHeap(introot,intindex){ intj,temp,finish; j=2*root; temp=R[root].key; finish=0; while(j<=index&&finish==0) { if(j<index) if(R[j].key<R[j+1].key) j++; if(temp>=R[j].key) finish=1; else { R[j/2].key=R[j].key; j=j*2; } } R[j/2].key=temp;}voidHeapSort(){ inti,j,temp,k; for(i=(L/2);i>=1;i--) CreateHeap(i,L); for(i=L-1,k=1;i>=1