數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告幾種排序算法的演示(附源代第四次實驗碼)畢業(yè)論文(編輯修改稿)
2025-07-19 21:28 本頁面
【文章內(nèi)容簡介】 n的歸并項，可用一次merge算法，將它們歸并成一個長度小于2len的歸并項。只剩下一個歸并項，其長度小于或等于len，[]中。偽代碼如下：template class typetemplate class typevoid sortlisttype::mergepass(sortlisttypeamp。sourcetable,sortlisttypeamp。mergedtable,const int len){ int i=0。 while(i+2*len=currentsize1)//表示至少有個子序列 { merge(sourcetable,mergedtable,i,i+len1,i+2*len1)。 i+=2*len。 } if(i+len=currentsize1)//若只有最后兩個子序列 merge(sourcetable,mergedtable,i,i+len1,currentsize1)。 else//若只有最后一個子序列 for(int j=i。j=currentsize1。j++) [j]=[j]。 if(len=currentsize1) {if(numcurrentsize) { cout第++num趟排序結(jié)果為:。 for(int t=0。tcurrentsize。t++) cout[t] 。 coutendl。 } }}歸并排序在一趟歸并算法的基礎(chǔ)上，實現(xiàn)兩路歸并排序算法。在兩路歸并排序算法中，[]中,[]中的歸并項兩兩歸并，[]中。[]中的歸并項兩兩歸并，[]中，如此反復(fù)進行。[]中，歸并趟數(shù)應(yīng)為偶數(shù)。如果做奇數(shù)趟就能完成時，最后還需要執(zhí)行一次一趟歸并過程，由于這時的歸并項長度len=n，因此在則趟歸并中while循環(huán)不執(zhí)行，[][]的工作。偽代碼如下：template class typevoid sortlisttype::mergesort(sortlisttype amp。table ){//按數(shù)據(jù)元素關(guān)鍵字非遞減的順序?qū)ε判虮韙able中數(shù)據(jù)元素進行遞歸排序 sortlisttype temptable。 int len=1。 while(lencurrentsize) { mergepass(table,temptable,len)。len*=2。 mergepass(temptable,table,len)。len*=2。 } num=0。} 9主函數(shù)主要功能是顯示主菜單，以及對各種排序的調(diào)用偽代碼如下：int main()//主函數(shù){ cout ***********************************************************************endl。cout 排序問題 endl。cout***********************************************************************endlendlendl。 int c=1。 char ch。 int n1=0。 while(c!=0) {cout\======================================================================endl。cout===================可供選擇的排序方法===========================endl。cout 1 直接插入排序 2 折半插入排序 endl。cout 3 冒泡排序 4 簡單選擇排序 endl。cout 5 快速排序 6 堆排序 endl。cout 7 歸并排序 0 退出排序程序 endl。 cout =======================================================================endl。cout\n 請輸入您需要的排序種類:。 cinch。 if(ch==39。039。) {cout 您已成功退出該系統(tǒng)!endl。system(pause)。 return 0。} int n,number。 if(ch=39。039。amp。amp。ch=39。739。) { cout\n 輸入您要進行排序的數(shù)的個數(shù)：。 cinn。 cout\n 請輸入n個數(shù)：。 sortlistinttable(n)。 for(int i=0。in。i++) {cinnumber。(i,number)。} switch(ch) { case 39。139。: cout\n *******您選擇的是直接插入排序*******\nendl。 ()。 break。 system(pause)。 break。 case 39。239。: cout\n *******您選擇的是折半插入排序*******\nendl。 ()。 break。 system(pause)。 break。 case 39。339。: cout\n *******您選擇的是冒泡排序*******\nendl。 ()。 break。 system(pause)。 break。 case 39。439。: cout\n *******您選擇的是簡單選擇排序*******\nendl。 ()。 break。 system(pause)。 break。 case 39。539。: cout\n *******您選擇的是快速排序*******\nendl。 (0,n1)。 break。 system(pause)。 break。 case 39。639。: cout\n *******您選擇的是堆排序*******\nendl。 ()。 break。 system(pause)。 break。 case 39。739。: cout\n *******您選擇的是歸并排序*******\nendl。 (table)。 break。 system(pause)。 break。 } } } system(pause)。 return 0。}三 上機結(jié)果及體會1) 實際完成的情況說明此程序主要實現(xiàn)了對不同排序算法的演示，并給出了每一趟的變化情況2) 程序的性能分析a. 直接插入排序（穩(wěn)定的排序方法）1時間復(fù)雜度a) 若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：2(n1)b)若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)： c) 若待排序記錄是隨機的，取最好和最壞情況的平均值關(guān)鍵字比較次數(shù)(約為)：記錄移動次數(shù)(約為)： 2空間復(fù)雜度：S(n)=O(1)b. 折半插入排序（穩(wěn)定的排序算法）就平均性能而言，因為折半查找優(yōu)于順序查找，所以折半插入排序也優(yōu)于直接插入排序。關(guān)鍵字的比較次數(shù)為：n*log2(n)c. 冒泡排序（穩(wěn)定的排序算法）1. 時間復(fù)雜度：a) 最好情況（正序）b) 比較次數(shù)：n1（只要進行一趟即可）c) 移動次數(shù)：0d) 最壞情況（逆序）e) 比較次數(shù)：（需n1趟，每趟達到最大比較次數(shù)） f) 移動次數(shù)：在最壞情況下，時間復(fù)雜度為:T(n)=O(n178。)2. 空間復(fù)雜度：S(n)=O(1)d. 簡單選擇排序（不穩(wěn)定的排序方法）1. 時間復(fù)雜度：O(n2)。2. 空間復(fù)雜度：S(1)。 e. 快速排序（不穩(wěn)定的排序方法）最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n178。) ：需?？臻g以實現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n) f. 堆排序（不穩(wěn)定的排序方法）] (nlog2n)。 2空間復(fù)雜性為O(1)。g. 歸并排序（穩(wěn)定的排序方法） 1時間復(fù)雜度為O(nlog2n)。 2空間復(fù)雜度為O(n）。 3）運行情況主菜單直接插入排序折半插入排序冒泡排序簡單選擇排序快速排序
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1