實(shí)驗(yàn)10：排序子系統(tǒng)

驗(yàn)證性實(shí)驗(yàn)10：排序子系統(tǒng)班級(jí)：H1001學(xué)號(hào)：09姓名：陸俊實(shí)驗(yàn)日期：2023.12.71．實(shí)驗(yàn)?zāi)康摹?〕掌握常用排序方法的根本思想?！?〕通過(guò)實(shí)驗(yàn)加深理解各種排序算法?！?〕通過(guò)實(shí)驗(yàn)掌握各種排序方法的時(shí)間復(fù)雜度分析?！?〕了解各種排序方法的優(yōu)缺點(diǎn)及適用范圍。2．實(shí)驗(yàn)內(nèi)容〔1〕編寫(xiě)直接插入排序程序?！?〕編寫(xiě)希爾排序程序?！?〕編寫(xiě)冒泡排序程序?！?〕編寫(xiě)快速排序程序?！?〕編寫(xiě)選擇排序程序。〔6〕編寫(xiě)歸并排序程序?！?〕編寫(xiě)堆排序程序。〔8〕程序執(zhí)行時(shí)，要求能顯示每一趟的排序結(jié)果?！?〕設(shè)計(jì)一個(gè)選擇式菜單，以菜單方式選擇上述排序程序。排序子系統(tǒng) *************************************************** *1------------更新排序數(shù)據(jù)* *2------------直接插入排序* *3------------希爾排序* *4------------冒泡排序* *5------------快速排序* *6------------選擇排序* *7------------歸并排序* *8------------堆排序* *0------------返回* ***************************************************請(qǐng)選擇菜單號(hào)〔0--8〕：3．實(shí)驗(yàn)程序#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請(qǐng)輸入%d個(gè)待排序數(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請(qǐng)選擇菜單號(hào)〔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請(qǐng)輸入%d個(gè)待排序數(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】鍵開(kāi)始排序〕："); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); num=0; QuickSort(1,L); printf("\n\t排序的最終結(jié)果是："); 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輸入出錯(cuò)！"); } 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按回車(chē)鍵返回。"); q=getchar(); if(q!='\xA') { getchar(); ch1='n'; } } }}voidInsertsort(){ inti,j,k,m=0; printf("\n\t原始數(shù)據(jù)為〔按【Enter】鍵開(kāi)始排序〕："); 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趟排序結(jié)果為〔按【Enter】鍵繼續(xù)〕：",m); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最終結(jié)果是："); 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】鍵開(kāi)始排序〕："); 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趟排序結(jié)果為〔按【Enter】鍵繼續(xù)〕：",m); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最終結(jié)果是："); for(i=1;i<=L;i++) printf("%5d",R[i].key); printf("\n");}voidBubblesort(){ inti,j,k; intexchange; printf("\n\t原始數(shù)據(jù)為〔按【Enter】鍵開(kāi)始排序〕："); 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趟排序結(jié)果為〔按【Enter】鍵繼續(xù)〕：",i); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } } printf("\n\t排序的最終結(jié)果是："); 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趟排序結(jié)果為〔按【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】鍵開(kāi)始排序〕："); 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趟排序結(jié)果為〔按【Enter】鍵繼續(xù)〕：",i); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最終結(jié)果是："); 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】鍵開(kāi)始排序〕："); 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趟排序結(jié)果為〔按【Enter】鍵繼續(xù)〕：",m); for(k=1;k<=L;k++) printf("%5d",R[k].key); getchar(); printf("\n"); } printf("\n\t排序的最終結(jié)果是："); 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