數(shù)據(jù)結(jié)構(gòu)-排序-實(shí)驗(yàn)報告 北郵

2011級數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告實(shí)驗(yàn)名稱：實(shí)驗(yàn)四排序?qū)W生姓名：班級：班內(nèi)序號： 學(xué)號：日期：2012年12月15日一，實(shí)驗(yàn)要求1，實(shí)驗(yàn)?zāi)康耐ㄟ^選擇下面兩個題目之一，學(xué)習(xí)、實(shí)現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。2，實(shí)驗(yàn)內(nèi)容使用簡單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法： 1、插入排序 2、希爾排序3、冒泡排序4、快速排序5、簡單選擇排序6、堆排序（選作）7、歸并排序（選作）8、基數(shù)排序（選作）9、其他要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計為3次移動）。3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間，精確到微秒（選作）4、對2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時間復(fù)雜度編寫測試main()函數(shù)測試線性表的正確性。三，程序分析存儲結(jié)構(gòu)一維數(shù)組關(guān)鍵算法分析直接插入排序：偽代碼：1）將整個待排序列的記錄序列劃分為有序區(qū)和無序區(qū)，初始時有序區(qū)為待排序記錄序列中的第一個記錄，無序區(qū)包括所有剩余待排序列記錄；2）將無序區(qū)的第一個記錄插入到有序區(qū)的合適位置中，從而使無序區(qū)減少一個記錄，有序區(qū)增加一個記錄；3）重復(fù)執(zhí)行，直到無序區(qū)沒有記錄為止。r[0]=r[i];//設(shè)置哨兵 for(intj=i-1;r[0]<r[j];j--)//尋找插入位置 { r[j+1]=r[j];//記錄后移 c2++;}順序時，時間復(fù)雜度為：O（n）逆序時，時間復(fù)雜度為：O（QUOTE）快速排序：偽代碼：1）．將i和j分別指向待排序區(qū)域的最左側(cè)記錄和最右側(cè)記錄的位置；2）．重復(fù)下述過程，直到i=j2.1右側(cè)掃描，直到記錄j的關(guān)鍵碼小于基準(zhǔn)記錄的關(guān)鍵碼；2.2如果i<j，則將r[j]與r[i]交換，并將i++；2.3左側(cè)掃描，直到記錄i的關(guān)鍵碼大于基準(zhǔn)記錄的關(guān)鍵碼；2.4如果i<j，則將r[i]與r[j]交換，并將j--；3）．退出循環(huán)，說明i和j指向了基準(zhǔn)記錄所在位置，返回該位置；關(guān)鍵算法：while(i<j) {while(i<j&&(c1++,r[i]<=r[j])) j--;//右側(cè)掃描if(i<j) { temp=r[i];//將較小記錄交換到ì前面 r[i]=r[j]; r[j]=temp;i++; c2+=3; }while(i<j&&(c1++,r[i]<=r[j])) i++;//左側(cè)掃描if(i<j) {temp=r[j]; r[j]=r[i];r[i]=temp;//將較大記錄交換到ì后面j--; c2+=3; }順序時，時間復(fù)雜度為：O(nlogn)逆序時，時間復(fù)雜度為：O（QUOTE）篩選法調(diào)整堆算法：偽代碼：1）設(shè)置i和j，分別指向當(dāng)前要篩選結(jié)點(diǎn)的左孩子；2）若節(jié)點(diǎn)i已是葉子，則篩選完畢；否則，比較要篩選結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)（若果有右孩子），并將j指向關(guān)鍵碼較大的結(jié)點(diǎn)；3）將要篩選結(jié)點(diǎn)i的關(guān)鍵碼與j所指向的結(jié)點(diǎn)的關(guān)鍵碼進(jìn)行比較3.1若果結(jié)點(diǎn)i的關(guān)鍵碼大，則完全二叉樹已經(jīng)是堆，篩選完畢；3.2否則將r【i】與r【j】交換；令i=j，轉(zhuǎn)步驟2繼續(xù)進(jìn)行篩選；關(guān)鍵算法：while(j<=m)//篩選還沒有進(jìn)行到葉子if(j<m&&r[j]<r[j+1]) j++;//比較i的左右孩子，j為較大者temp=r[i]; r[i]=r[j]; r[j]=temp;//將根結(jié)點(diǎn)與結(jié)點(diǎn)j交換堆排序算法：偽代碼：1）定義所需參數(shù)i和temp；2）調(diào)用Sift(intr[],intk,intm)對數(shù)據(jù)建堆，每建完一次后將堆得第一項(xiàng)數(shù)存儲如數(shù)組，不再參加下次的建堆；3）直到待參加建堆的數(shù)的項(xiàng)數(shù)減少為零時，排序完畢，輸出排序結(jié)果關(guān)鍵算法：for(i=n;i>=0;i--)//重復(fù)執(zhí)行移走堆頂及重建堆的操作{ c2+=3; temp=r[i]; r[i]=r[0]; r[0]=temp;Sift(r,0,i-1);}時間復(fù)雜度為：O(nlogn)歸并排序關(guān)鍵算法if(r[i]<=r[j])r1[k++]=r[i++];//取r[i]和r[j]中較小者放入r1[k]while(i<=m)//若第一個子序列沒處理完，則進(jìn)行收尾處理 r1[k++]=r[i++];while(i<=n-2*h+1)//待歸并記錄至少有兩個長度為h的子序列 { Merge(r,r1,i,i+h-1,i+2*h-1); i+=2*h;}時間復(fù)雜度為：O(nlogn)四，程序運(yùn)行結(jié)果測試主函數(shù)的流程輸出結(jié)果輸出結(jié)果結(jié)束直接排序希爾排序起泡排序簡單選擇排序堆排序快速排序歸并排序選擇要用的排序方法開始輸入數(shù)據(jù)的項(xiàng)數(shù)選擇測試數(shù)據(jù)的產(chǎn)生方法自己輸入隨即產(chǎn)生輸出產(chǎn)生的數(shù)據(jù)121234567測試結(jié)果從測試結(jié)果來看，這幾種排序在時間復(fù)雜性，空間復(fù)雜性，穩(wěn)定性等方面存在差別。從最好的情況看，直接插入排序和起泡排序的時間復(fù)雜性最好。從最壞情況看，快速排序的時間復(fù)雜性最好，對直接選擇排序，堆排序和歸并排序影響不大。還有隨著待排序的數(shù)據(jù)個數(shù)numv大小，各個排序有各自的優(yōu)缺點(diǎn)。Numv越小，采用簡單排序方法越合適，numv越大，采用改進(jìn)的排序方法越合適。五．總結(jié)調(diào)試時出現(xiàn)的問題及解決的方法調(diào)試時還幾個排序都是有些項(xiàng)不參加排序，或者就是輸出一個非輸入數(shù)據(jù)的小數(shù)。后來發(fā)現(xiàn)這些都是排序中的循環(huán)的起始位置和終止位置有問題。后來邊測試邊改了，就基本完成了。心得體會這次實(shí)驗(yàn)我覺得是做的實(shí)驗(yàn)題目中相對之下較簡單的一種，好多都是書上的知識，只要將書中一些不合理的改正就好。對于計算比較次數(shù)和移動次數(shù)的思路也是很容易想到的，只要對每個排序的工作原理，就能慢慢的加上計數(shù)的算法。對于實(shí)驗(yàn)課和理論課，我始終覺得上課和上機(jī)之間差別很大，自己動手做起來的時候，好多問題都會出現(xiàn)。當(dāng)然有了理論的基礎(chǔ)，想算法，方案時也就少走一些彎路。經(jīng)過實(shí)驗(yàn)課，不僅對書本知識有了進(jìn)一步的掌握，理解，更重要的是提升了自己的應(yīng)用知識的能力。多做幾個實(shí)驗(yàn)題，對自己的知識有很大的提升，還可以培養(yǎng)我們分析問題，解決問題的方法。盡管編程實(shí)驗(yàn)在編不出來時，心情會很煩躁，確實(shí)是一件痛苦的事。但最后做完