各種排序算法演示

課程設(shè)計(jì)（論文）任務(wù)書 學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù) 專 業(yè)_2005-1 班一、 課程設(shè)計(jì)（論文）題目 二、 課程設(shè)計(jì)（論文）工作自2007年6月五日起至2007年7月丄日止。三、 課程設(shè)計(jì)（論文）地點(diǎn):多媒體實(shí)驗(yàn)室（5-302,303） 四、 課程設(shè)計(jì)（論文）內(nèi)容要求：1?本課程設(shè)計(jì)的目的 （1） 熟練掌握C語(yǔ)言的基本知識(shí)和技能; （2） 掌握各種排序（直接插入，希爾，冒泡，快速排序，簡(jiǎn)單選擇，堆排序）方法及適用場(chǎng)合，并能在解決實(shí)際問題時(shí)靈活應(yīng)用; （3） 從空間和時(shí)間的角度分析各種排序; （5）培養(yǎng)分析、解決問題的能力；提高學(xué)生的科技論文寫作能力。 —課程設(shè)計(jì)的任務(wù)及要求 —1） 基本要求: （1） 設(shè)計(jì)一個(gè)的菜單將在實(shí)現(xiàn)的功能顯示出來，并有選擇提示;（2） 分別實(shí)現(xiàn)直接插入，希爾，冒泡，快速排序，簡(jiǎn)單選擇，堆排序算法；（3） 通過多種測(cè)試數(shù)據(jù)，對(duì)各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行比較并說明在實(shí)際場(chǎng)合的運(yùn)用。 2） 創(chuàng)新要求: 提高算法效率，降低時(shí)間復(fù)雜度和空間復(fù)雜度 3） 課程設(shè)計(jì)論文編寫要求 （1） 要按照課程設(shè)計(jì)模板的規(guī)格書寫課程設(shè)計(jì)論文 （2） 論文包括目錄、正文、心得體會(huì)、參考文獻(xiàn)等 （3） 課程設(shè)計(jì)論文用B5紙統(tǒng)一打印，裝訂按學(xué)校的統(tǒng)一要求完成 4） 答辯與評(píng)分標(biāo)準(zhǔn): （1） 完成原理分析：20分; （2） 完成設(shè)計(jì)過程：40分;（3） 完成調(diào)試：20分；（4） 回答問題：20分。5） 參考文獻(xiàn)：（1） 嚴(yán)蔚敏，吳偉民?數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，2006.（2） 嚴(yán)蔚敏、吳偉民、米寧?數(shù)據(jù)結(jié)構(gòu)題集。北京：清華大學(xué)出版社，2006.（3）譚浩強(qiáng).C程序設(shè)計(jì)（第二版）作者：清華大學(xué)出版社，2006.6） 課程設(shè)計(jì)進(jìn)度安排內(nèi)容 天數(shù) 地點(diǎn)構(gòu)思及收集資料 2 圖書館編程設(shè)計(jì)與調(diào)試 5 實(shí)驗(yàn)室撰寫論文 3 圖書館、實(shí)驗(yàn)室學(xué)生簽名： 年月日課程設(shè)計(jì)（論文）評(píng)審意見（1）完成原理分析（20分）：優(yōu)（）、良（、、中（、、一般（、、差（);（2）設(shè)計(jì)分析 （20分）：優(yōu)（）、良（、、中（、、一般（、、差（);（3）完成調(diào)試 （20分）：優(yōu)（）、良（、、中（、、一般（、、差（);（4）翻譯能力 （20分）：優(yōu)（）、良（、、中（、、一般（、、差（);（5）回答問題 （20分）：優(yōu)（）、良（、、中（、、一般（、、差（);（6）格式規(guī)范性及考勤是否降等級(jí)：是（）、否（）評(píng)閱人： 職稱： 年月日目錄TOC\o"1-5"\h\z一、 問題描述 4\o"CurrentDocument"二、內(nèi)容簡(jiǎn)介 4\o"CurrentDocument"2.1基本要求： 4\o"CurrentDocument"2.2.算法思想： 5\o"CurrentDocument"2.3.模塊劃分： 7\o"CurrentDocument"2.4.數(shù)據(jù)結(jié)構(gòu)： 7\o"CurrentDocument"2.5.源程序： 7\o"CurrentDocument"2.6.測(cè)試情況： 20\o"CurrentDocument"三、小結(jié) 24\o"CurrentDocument"四、參考文獻(xiàn) 25問題描述分別實(shí)現(xiàn)直接插入、希爾、冒泡、快速排序、簡(jiǎn)單選擇、堆排序的算法。分別從空間和時(shí)間的角度來分析各種排序的。通過測(cè)試多組數(shù)據(jù)來掌握各種排序的方法及適用場(chǎng)合，并能在解決實(shí)際問題靈活運(yùn)用。在編寫代碼的時(shí)候，有以下幾個(gè)問題：（1）建立一個(gè)主函數(shù)，在主函數(shù)中要有菜單界面，和輸入功能鍵相應(yīng)執(zhí)行的功能。并且要求能循環(huán)使用系統(tǒng)。（2）分別實(shí)現(xiàn)直接插入、希爾、冒泡、快速排序、簡(jiǎn)單選擇、堆排序的算法。（3）通過輸入不同的數(shù)據(jù)數(shù)組，來測(cè)試每組數(shù)據(jù)用那種排序算法最優(yōu)。二、內(nèi)容簡(jiǎn)介2.1基本要求：分別實(shí)現(xiàn)直接插入，希爾，冒泡，快速排序，簡(jiǎn)單選擇，堆排序算法；設(shè)計(jì)一個(gè)菜單將要實(shí)現(xiàn)的功能顯示出來。通過測(cè)試多組數(shù)據(jù)對(duì)各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行比較并說明在實(shí)際場(chǎng)合的運(yùn)用。在實(shí)現(xiàn)這六種排序算法的過程中，首先要建立一個(gè)靜態(tài)的說明頁(yè)面，把每個(gè)功能鍵對(duì)應(yīng)的操作給一一說明，能讓使用者快速的進(jìn)入用戶的角色。進(jìn)入系統(tǒng)時(shí)，需要提示用戶下一步應(yīng)該輸入什么功能鍵，并且要讓用戶清楚的知道輸入了此功能鍵以后將進(jìn)入什么排序系統(tǒng)中。進(jìn)入相應(yīng)的排序系統(tǒng)后，要提示用戶輸入一組需要排序的數(shù)據(jù)，輸入數(shù)據(jù)組后，系統(tǒng)要依次顯示出未排序前數(shù)據(jù)的位置，排序后數(shù)據(jù)的位置，在排序過程中交換或比較的次數(shù)，排序的趟樹，還有此種排序時(shí)間的消耗，并提示按任意鍵繼續(xù)系統(tǒng)。并且要構(gòu)建一個(gè)對(duì)于同一個(gè)數(shù)據(jù)數(shù)組，依次用所有的排序算法給其排序后，輸出對(duì)應(yīng)排序算法的時(shí)間效率，再經(jīng)過系統(tǒng)比較后，輸出在所有排序方法中時(shí)間效率最優(yōu)的排序算法，如果時(shí)間相等，則都輸出。系統(tǒng)要可以循環(huán)使用，若要退出系統(tǒng)，則只需輸入e功能鍵即可！2.2.算法思想：1． 直接插入排序的基本思想是基于插入，開始假定第一個(gè)記錄有序，然后從第二個(gè)記錄開始，依次插入到前面有序的子文件中。即將記錄R[i](2<=i<=n)插入到有序子序列R[l..iT]中，使記錄的有序序列從R[l..i-1]變?yōu)镽[l..i],最終使整個(gè)文件有序。共進(jìn)行n-1趟插入。最壞時(shí)間復(fù)雜度是0(厲)，平均時(shí)間復(fù)雜度是0(n2)，空間復(fù)雜度是O(1)，是穩(wěn)定排序。簡(jiǎn)單選擇排序的基本思想是基于選擇，開始有序序列長(zhǎng)度為零，第i(l〈二i〈n)趟簡(jiǎn)單選擇排序是，從無序序列R[i..n]的n-i+1記錄中選出關(guān)鍵字最小的記錄，和第i個(gè)記錄交換，使有序序列逐步擴(kuò)大，最后整個(gè)文件有序。共進(jìn)行n-1趟選擇。最壞時(shí)間復(fù)雜度是0(n2),平均時(shí)間復(fù)雜度是0(n2),空間復(fù)雜度是0(1),是不穩(wěn)定排序。希爾排序：先將整個(gè)待排記錄分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序冒泡排序：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序，則將兩個(gè)記錄交換，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。依此類推，直到第N-1和第N個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止。上述為第一趟排序，其結(jié)果使得關(guān)鍵字的最大紀(jì)錄被安排到最后一個(gè)記錄的位置上。然后進(jìn)行第二趟起泡排序，對(duì)前N-1個(gè)記錄進(jìn)行同樣操作。一共要進(jìn)行N-1趟起泡排序快速排序思想：首先將待排序記錄序列中的所有記錄作為當(dāng)前待排序區(qū)域，以第一個(gè)記錄的關(guān)鍵字作為樞軸(或支點(diǎn))(pivot),凡其關(guān)鍵字不大于樞軸的記錄均移動(dòng)至該記錄之前，凡關(guān)鍵字不小于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無序序列R[s..t]將分割成兩部分：R[s..i-1]和R[i+l..t]，且R[j].keyWR[i].keyWR[k].key(sWjvi,ivkWt),然后再遞歸地將R[s..i-1]和R[i+1..t]進(jìn)行快速排序?？焖倥判蛟谟涗浻行驎r(shí)蛻變?yōu)槊芭菖判颍捎谩叭呷≈小狈ǜ纳破湫阅?，避免最壞情況的出現(xiàn)。堆排序基本思想是：堆是n個(gè)元素的序列，先建堆，即先選得一個(gè)關(guān)鍵字最大或最小的記錄，然后與序列中最后一個(gè)記錄交換，之后將序列中前n-1記錄重新調(diào)整為堆(調(diào)堆的過程稱為“篩選”)，再將堆頂記錄和當(dāng)前堆序列的最后一個(gè)記錄交換，如此反復(fù)直至排序結(jié)束。優(yōu)點(diǎn)是在時(shí)間性能與樹形選擇排序?qū)偻涣考?jí)的同時(shí)，堆排序只需要一個(gè)記錄大小供交換用的輔助空間，調(diào)堆時(shí)子女只和雙親比較避免了過多的輔助存儲(chǔ)空間及和最大值的比較，主函數(shù)）2.3.模塊劃分：voidInsertSort(RECNODE*r,intn)直接插入排序voidBubleSort(RECNODE*r,intn)冒泡排序intPartition(RECNODE*r,int*low,int*high)一躺快速排序voidQuickSort(RECNODE*r,intstart,intend)快速排序voidSeleSort(RECNODE*r,intn)直接選擇排序voidShellSort(RECNODE*r,intn)希爾排序voidSift(RECNODE*r,inti,intm)voidHeapSort(RECNODE*r,intn)堆排序voidBubleSort(doublea[])時(shí)間數(shù)組的冒泡排序doubleTInsertSort(intlen,RECNODE*a,intp)直接插入排序時(shí)間測(cè)試doubleTBubleSort(intlen,RECNODE*a,intp)冒泡排序時(shí)間測(cè)試doubleTQuickSort(intlen,RECNODE*a,intp)快速排序時(shí)間測(cè)試doubleTSeleSort(intlen,RECNODE*a,intp)直接選擇排序時(shí)間測(cè)試doubleTShellSort(intlen,RECNODE*a,intp)希爾排序時(shí)間測(cè)試doubleTHeapSort(intlen,RECNODE*a,intp)堆排序時(shí)間測(cè)試2.4.數(shù)據(jù)結(jié)構(gòu)：typedefstruct{intkey;//關(guān)鍵字}RECNODE;結(jié)構(gòu)體2.5.源程序：#defineMAXSIZE50#include<stdio.h>#include<iostream>#include<ctime>#include<windows.h>#include<cmath>usingnamespacestd;typedefstruct{intkey;}RECNODE;intb,t;//b為記錄交換的次數(shù)，t為記錄排序的趟數(shù)intMakeList(RECNODE*r){intj,k;printf("請(qǐng)輸入初始數(shù)據(jù)(每個(gè)數(shù)據(jù)以空格隔開，-1結(jié)束)：")；k=0;scanf("%d",&j);while(j!=-1){k++;r[k].key=j;scanf("%d",&j);}returnk;}//輸入要排序的一組數(shù)據(jù)，并且返回?cái)?shù)據(jù)的個(gè)數(shù)，以-1為結(jié)束標(biāo)志////////////////////////////////////////////////////////////////////////voidUndealoutList(RECNODE*r,intn){inti;printf("未排序前的數(shù)據(jù)：")；for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n");}voidDealoutList(RECNODE*r,intn){inti;printf("排序后的數(shù)據(jù)：")；for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n");printf("交換或比較的次數(shù)：％d\n",b);printf("排序的趟數(shù)：％d\n",t);}////////////////////////////////////////////////////////////////////////voidInsertSort(RECNODE*r,intn)//直接插入排序///*實(shí)現(xiàn)“直接插入排序”可分三步進(jìn)行：1.利用“順序查找”實(shí)現(xiàn)在R[1..i-1]中查找R[i]的插入位置，R[1..j].key?R[i].key<R[j+1..i-1].key；將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；將R[i]插入(復(fù)制)到R[j+1]的位置上。*/{inti,j;b=0,t=0;//b為記錄交換的次數(shù)，t為記錄排序的趟數(shù)for(i=2;i<=n;i++){r[0]=r[i];//r[0]的作用是暫存空間j=i-1;while(r[0].key<r[j].key)//如果目標(biāo)數(shù)比源數(shù)小{r[j+1]=r[j];//則讓大的數(shù)從后往前依次往后挪一個(gè)位置，然后讓小數(shù)插入到恰當(dāng)位置j--;b++;}r[j+1]=r[0];b++;t++;}}////////////////////////////////////////////////////////////////////////voidBubleSort(RECNODE*r,intn)//冒泡排序{inti,j;b=0,t=0;//b為記錄交換的次數(shù)，t為記錄排序的趟數(shù)RECNODEtemp;//暫寸空間for(i=1;i<n;i++){for(j=n-1;j>=i;j--)//目標(biāo)數(shù)是從第一個(gè)數(shù)開始，被比較數(shù)從最后一個(gè)開始if(r[j+1].key<r[j].key)//如果目標(biāo)數(shù)比其下一個(gè)數(shù)要大{ //則兩數(shù)交換，下一趟比較則還是用原目標(biāo)數(shù)與其下一個(gè)書比較temp=r[j+1];r[j+1]=r[j];r[j]=temp;b++;}elseb++;//否則不用交換，繼續(xù)和下一個(gè)數(shù)比較t++;}}////////////////////////////////////////////////////////////////////////voidBubleSort(doublea[])//時(shí)間數(shù)組的冒泡排序{inti,j;b=0,t=0;doubletemp;for(i=1;i<7;i++){for(j=5;j>=i;j--)if(a[j+1]<a[j]){temp=a[j+1];a[j+1]=a[j];a[j]=temp;b++;}elseb++;t++;}}////////////////////////////////////////////////////////////////////////intPartition(RECNODE*r,int*low,int*high)//—躺快速排序///*找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。*/inti,j;staticintw=0;RECNODEtemp;i=*low;//i指向第一個(gè)數(shù)j=*high;temp=r[i];//暫存單元，存著目標(biāo)數(shù)do{ //當(dāng)目標(biāo)數(shù)小于等于要比較的數(shù)，并且目標(biāo)數(shù)在左邊while((r[j].key>=temp.key)&&(i<j)){j--;//則不用換，只要讓指向要比較的數(shù)的位置左移一位w++;}if(i<j)//若遇到一個(gè)在目標(biāo)數(shù)右邊的小數(shù){r[i]=r[j];//則將小數(shù)賦給目標(biāo)數(shù)原來所在的位置i++;//要比較的數(shù)的位置右移一位w++;}while((r[i].key<=temp.key)&&(i<j))//同理比較，只是現(xiàn)在要比較的數(shù)在目標(biāo)數(shù)的右邊{i++;w++;}if(i<j){r[j]=r[i];j--;w++;}}while(i!=j);r[i]=temp;b=w;//b為記錄交換的次數(shù)returni;}voidQuickSort(RECNODE*r,intstart,intend)//快速排序{inti;staticintq=0;if(start<end){i=Partition(r,&start,&end);q++;QuickSort(r,start,i-l);//對(duì)低子表遞歸排序，i為中間位置QuickSort(r,i+1,end);//對(duì)高子表遞歸排序}t=q;//t為記錄排序的趟數(shù)}////////////////////////////////////////////////////////////////////////voidSeleSort(RECNODE*r,intn)//直接選擇排序////每次都是將無序序列中的最小的數(shù)找到，然后依次放到有序序列的最后{inti,j,z;b=0,t=0;//b為記錄交換的次數(shù)，t為記錄排序的趟數(shù)RECNODEtemp;for(i=1;i<n;i++){z=i;for(j=i+1;j<=n;j++)//從第i個(gè)后的序列中選出最小的一個(gè)數(shù)if(r[j].key<r[z].key){z=j;b++;}elseb++;if(z!=i){temp=r[i];r[i]=r[z];r[z]=temp;}t++;}////////////////////////////////////////////////////////////////////////voidShellSort(RECN0DE*r,intn)//希爾排序//{inti,j,dk;//dk記錄前后位置的增量b=0,t=0;dk=n/2;while(dk>0)//一趟增量為dk的插入排序{for(i=dk+1;i<=n;++i)if(r[i].key〈r[i-dk].key)//將r[i]插入有序增量子表{r[0]=r[i];//r[0]為暫存單元for(j=i-dk;j>0&&r[0].key〈r[j].key;j-=dk){r[j+dk]=r[j];b++;//記錄后移，查找插入位置}r[j+dk]=r[0];}dk=dk/2;//增量改為原來的一半t++;}}////////////////////////////////////////////////////////////////////////voidSift(RECNODE*r,inti,intm){intj;staticintx=0;RECNODEtemp;temp=r[i];j=2*i;while(j<=m)//沿key較大的孩子結(jié)點(diǎn)向下篩選{if(j〈m&&(r[j].key〈r[j+l].key))//j為key較大的記錄的下標(biāo){}if(temp.key<r[j].key){r[i]=r[j];i=j;j=2*i;x++;}elsex++;break;}r[i]=temp;b=x;}voidHeapSort(RECNODE*r,intn)//堆排序{RECNODEtemp;inti;t=0;for(i=n/2;i>=1;--i)Sift(r,i,n);//建大頂堆for(i=n;i>=2;--i)//將堆頂記錄和當(dāng)前未經(jīng)排序子序列//H.r[1..i]中最后一個(gè)記錄相互交換{temp=r[1];r[1]=r[i];r[i]=temp;Sift(r,1,i-1);//對(duì)H.r[1]進(jìn)行篩選t++;}}////////////////////////////////////////////////////////////////////////doubleTInsertSort(intlen,RECNODE*a,intp){if(p!=7){len=MakeList(a);UndealoutList(a,len);}//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間LARGE_INTEGERm_liPerfFreq={0};QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);InsertSort(a,len);if(p!=7){DealoutList(a,len);}LARGE_INTEGERliPerfNow={0};QueryPerformanceCounter(&liPerfNow);doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;cout〈〈"直接插入排序時(shí)間消耗:”<<time〈〈"MS"〈〈"\n";return(time);}//直接插入排序時(shí)間測(cè)試////////////////////////////////////////////////////////////////////////doubleTBubleSort(intlen,RECNODE*a,intp){if(p!=7)//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間{len=MakeList(a);UndealoutList(a,len);}LARGE_INTEGERm_liPerfFreq={0};QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);BubleSort(a,len);if(p!=7){DealoutList(a,len);}LARGE_INTEGERliPerfNow={0};QueryPerformanceCounter(&liPerfNow);doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;cout〈〈”冒泡排序序時(shí)間消耗：”〈〈time〈〈”MS”〈〈”\n”；return(time);}//冒泡排序時(shí)間測(cè)試////////////////////////////////////////////////////////////////////////doubleTQuickSort(intlen,RECNODE*a,intp){if(p!=7){len=MakeList(a);UndealoutList(a,len);}//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間LARGE_INTEGERm_liPerfFreq={0};QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);QuickSort(a,1,len);if(p!=7){DealoutList(a,len);}//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間LARGE_INTEGERliPerfNow={0};QueryPerformanceCounter(&liPerfNow);doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;cout〈〈"快速排序時(shí)間消耗:”<<time〈〈"MS"〈〈"\n";return(time);}//快速排序時(shí)間測(cè)試////////////////////////////////////////////////////////////////////////doubleTSeleSort(intlen,RECNODE*a,intp){if(p!=7){len=MakeList(a);UndealoutList(a,len);}LARGE_INTEGERm_liPerfFreq={0};QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);SeleSort(a,len);if(p!=7){DealoutList(a,len);}//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間LARGE_INTEGERliPerfNow={0};QueryPerformanceCounter(&liPerfNow);doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;cout〈〈”直接選擇排序時(shí)間消耗:”〈〈time〈〈”MS”〈〈”\n”；return(time);}//直接選擇排序時(shí)間測(cè)試////////////////////////////////////////////////////////////////////////doubleTShellSort(intlen,RECNODE*a,intp){if(p!=7){len=MakeList(a);UndealoutList(a,len);}LARGE_INTEGERm_liPerfFreq={0};QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);ShellSort(a,len);if(p!=7){DealoutList(a,len);}//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間LARGE_INTEGERliPerfNow={0};QueryPerformanceCounter(&liPerfNow);doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;cout〈〈"希爾排序時(shí)間消耗："〈〈time〈〈"MS"〈〈"\n";return(time);}//希爾排序時(shí)間測(cè)試////////////////////////////////////////////////////////////////////////doubleTHeapSort(intlen,RECNODE*a,intp){if(p!=7)//若為時(shí)間效率全比較，則不用把比較的具體過程輸出，只需輸出排序時(shí)間{len=MakeList(a);UndealoutList(a,len);}LARGE_INTEGERm_liPerfFreq={0};QueryPerformanceFrequency(&m_liPerfFreq);LARGE_INTEGERm_liPerfStart={0};QueryPerformanceCounter(&m_liPerfStart);HeapSort(a,len);if(p!=7){DealoutList(a,len);}LARGE_INTEGERliPerfNow={0};QueryPerformanceCounter(&liPerfNow);doubletime=liPerfNow.QuadPart-m_liPerfStart.QuadPart;time/=m_liPerfFreq.QuadPart;cout〈〈"堆排序時(shí)間消耗:”〈〈time〈〈"MS"〈〈"\n";return(time);}//堆排序時(shí)間測(cè)試////////////////////////////////////////////////////////////////////////voidmain()

doubleTIMES[7],TIMES1[7];RECNODEa[MAXSIZE];intlen,p;do{指導(dǎo)老師：劉艷麗程序員：徐園園3號(hào)05指導(dǎo)老師：劉艷麗程序員：徐園園3號(hào)05計(jì)算機(jī)一班※※※※※※※※菜單※※※※※※※※printf(”☆★ ☆★、『)；☆★\n");★☆\n");☆★\n");★☆\n");☆★\n");☆★\n");★☆\n");☆★\n");☆★\n"); 直接插入排序 ☆★\n");★☆\n");☆★\n");★☆\n");☆★\n");☆★\n");★☆\n");☆★\n");☆★\n"); 直接插入排序 ******************★☆、『); 冒泡排序 ********************\n"); 快速排序 ********************\n"); 直接選擇排序 ********************\n"); 堆排序 ********************\n"); 希爾排序 ********************\n"); 時(shí)間效率比較 ********************\n");(0) 退出 ********************\n");switch(p){case1:printf("直接插入排序\n");TInsertSort(len,a,p); break;//直接插入排序case2:printf("冒泡排序\n");TBubleSort(len,a,p); break;//冒泡排序case3:printf("快速排序\n");TQuickSort(len,a,p); break;//快速排序case4:printf("直接選擇排序\n");TSeleSort(len,a,p); break;//直接選擇排序case5:printf("堆排序\n");THeapSort(len,a,p); break;//堆排序case6:printf("希爾排序\n");TShellSort(len,a,p); break;//希爾排序case7:printf("時(shí)間效率比較\n");{len二MakeList(a);UndealoutList(a,len);TIMES1[1]=TIMES[1]=TInsertSort(len,a,p);TIMES1[2]=TIMES[2]=TBubleSort(len,a,p);TIMES1[3]=TIMES[3]=TQuickSort(len,a,p);TIMES1[4]=TIMES[4]=TSeleSort(len,a,p);TIMES1[5]=TIMES[5]=THeapSort(len,a,p);TIMES1[6]=TIMES[6]=TShellSort(len,a,p);BubleSort(TIMES);printf("\n");if(TIMES[l]==TIMESl[l])printf(〃排序這組數(shù)據(jù)用直接插入排序時(shí)間最短!\n〃)；if(TIMES[l]==TIMESl[2])printf(〃排序這組數(shù)據(jù)用冒泡排序時(shí)間最短!\n〃)；if(TIMES[l]==TIMESl[3])printf(〃排序這組數(shù)據(jù)用快速排序時(shí)間最短!\n〃)；if(TIMES[l]==TIMESl[4])printf(〃排序這組數(shù)據(jù)用直接選擇排序時(shí)間最短!\n");if(TIMES[l]==TIMESl[5])printf(〃排序這組數(shù)據(jù)用堆排序時(shí)間最短!\n〃)；if(TIMES[l]==TIMESl[6])printf(〃排序這組數(shù)據(jù)用希爾排序時(shí)間最短!\n〃)；break;}//時(shí)間效率全比較case0: break;//退出default:printf("輸入錯(cuò)誤!請(qǐng)重新輸入!\n");break;}system("pause");//系統(tǒng)暫停，提示按任意鍵繼續(xù)。。。。}while(p!=0);//fordo}

2.6.測(cè)試情況：XJ<XJ<XJ<XJ<XJ<XJ<XJ<靈上卬零蘭京"占申，序糸字充*EXJ<XJ<XJ<XJ<XJ<XJ<XJ<指導(dǎo)老師：劉艷麗程序員：徐園園3號(hào)跖計(jì)算機(jī)一班3K3K丸 匚K匚￡亍hehehehehehehe€4〉—育 詵申序丸 匚(3K「 ■'l|匚(卜匚★☆xmmx(?> 時(shí)間嫌率比較￡亍HEHEHEHEHEHEXX(0) ]艮出址■■數(shù)1??次63號(hào)序數(shù)數(shù)篇.?序繼序?qū)５臄?shù)饕進(jìn)述入初土刖的比趟入意上插入晉或的插任在嚴(yán)翳徙雯-WS供晝稟龔x^w請(qǐng)各98弔89HJ7簾564P5Bn421

^21

s162

吟36985746859-4Hs78654213548舌$、、申e■序XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<

g序XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<XJ<★宅訃HEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHEHExjc^l^才請(qǐng)?jiān)谏鲜鲂蛱?hào)中選擇一個(gè)并輸入:首先顯示綜合排序系統(tǒng)的界面，然后提示輸入菜單中的子選項(xiàng)，現(xiàn)輸入1，進(jìn)入直接插入排序的界面。

進(jìn)入直接插入排序的界面后，系統(tǒng)提示要輸入需要排序的一組數(shù)據(jù)，并且以-1為結(jié)束符。先輸入12456789984536-1，系統(tǒng)會(huì)依次顯示出未排序前數(shù)據(jù)的位置，排序后數(shù)據(jù)的位置，在排序過程中交換或比較的次數(shù)，排序的趟樹，還有直接插入排序時(shí)間的消耗，并提示按任意鍵繼續(xù)系統(tǒng)?，F(xiàn)選擇2，則進(jìn)入冒泡排序的界面。如下：79UT1.■78F^M9779UT1.■78F^M97稚88七工44dA62.k51居4爭(zhēng)9=A%28162，叮3唇:數(shù)I??次7間續(xù)數(shù)數(shù)番??時(shí)繼始的數(shù)齧序鍵述序初前的比趟匱S上排入誓或的排任左SI盂亠畫按Ms78798465421636594進(jìn)入冒泡排序的界面，排序好后，輸入3，進(jìn)入快速排序868965868965456543十0000^7-9965格456苫554針89^36才3Ms??■耗-中薯..次58號(hào)數(shù)數(shù)篇:8序始的數(shù)饕紅述序初前的比趟蜃思上排入晉或的排任在速蠱按進(jìn)入快速排序的界面，排序好后，輸入4，進(jìn)入直接選擇排序,-1纟吉束）:4587436578912-189126587,-1纟吉束）:4587436578912-18912658763439-78據(jù)呂7數(shù)45236??數(shù)MS中薯.?次8S號(hào)序數(shù)數(shù)番：序繼序范的數(shù)饕餐述擇初前的比趟擇意上選入書或的選任注豊果琵請(qǐng)進(jìn)入直接選擇排序的界面，排序好后，輸入5，進(jìn)入堆排序-178945G239843156R?

士口8

194,5幵68456隔32牝9炷48P-3nj-n15婁6每：縱I??次7整數(shù)數(shù)番:1始的數(shù)饕燼初前的比趟時(shí)意上序入嘗或的序任在^^al啜序徙伎雇稟姜請(qǐng)Ms1323進(jìn)入堆排序的界面，排序好后，輸入3，進(jìn)入希爾排序,-丄纟吉東）:3265684512987864-19878646878985格445

空682以53據(jù)￡12數(shù)326112個(gè)4嗨：勲I??次31數(shù)數(shù)番:i始的數(shù)叢綣述序初前的比趟屢S上排入昔或的排任在爾輸連塞序爾fe進(jìn)入希爾排序的界面，排序好后，輸入7