實驗10：排序子系統(tǒng)

驗證性實驗10：排序子系統(tǒng)班級：H1001學號：09姓名：陸俊實驗日期：2023.12.71．實驗目的〔1〕掌握常用排序方法的根本思想?！?〕通過實驗加深理解各種排序算法。〔3〕通過實驗掌握各種排序方法的時間復雜度分析。〔4〕了解各種排序方法的優(yōu)缺點及適用范圍。2．實驗內(nèi)容〔1〕編寫直接插入排序程序。〔2〕編寫希爾排序程序。〔3〕編寫冒泡排序程序?！?〕編寫快速排序程序?！?〕編寫選擇排序程序?！?〕編寫歸并排序程序?！?〕編寫堆排序程序。〔8〕程序執(zhí)行時，要求能顯示每一趟的排序結果?！?〕設計一個選擇式菜單，以菜單方式選擇上述排序程序。排序子系統(tǒng) *************************************************** *1------------更新排序數(shù)據(jù)* *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個待排序數(shù)據(jù)〔按【Enter】鍵分隔〕：\n\t",L); for(i=1;i<=L;i++) { scanf("%d",&S[i].key); getchar(); printf("\t"); } printf("\n\t排序數(shù)據(jù)已經(jīng)輸入完畢！"); ch1='y'; while(ch1=='y'||ch1=='Y') { printf("\n"); printf("\n\t\t排序子系統(tǒng)"); printf("\n\t\t***************************************************"); printf("\n\t\t*1------------更新排序數(shù)據(jù)*"); 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個待排序數(shù)據(jù)〔按【Enter】鍵分隔〕：\n\t",L); for(i=1;i<=L;i++) { scanf("%d",&S[i].key); getchar(); printf("\t"); } printf("\n\t排序數(shù)據(jù)已經(jīng)輸入完畢！"); break; case'2':Insertsort();break; case'3':Shellsort();break; case'4':Bubblesort();break; case'5':printf("\n\t原始數(shù)據(jù)為〔按【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原始數(shù)據(jù)為〔按【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】鍵繼續(xù)〕：",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原始數(shù)據(jù)為〔按【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】鍵繼續(xù)〕：",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原始數(shù)據(jù)為〔按【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】鍵繼續(xù)〕：",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】鍵繼續(xù)〕：",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原始數(shù)據(jù)為〔按【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】鍵繼續(xù)〕：",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內(nèi)存容量不夠！"); 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原始數(shù)據(jù)為〔按【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】鍵繼續(xù)〕：",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