幾種排序算法分析

《幾種排序算法分析》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。

1、《幾種排序算法的分析》摘要：排序算法是在C++中經常要用到的一種重要的算法。如何進行排序，特別是高效率的排序是是計算機應用屮的一個重要課題。同一個問題可以構造不同的算法，最終選擇哪一個好呢？這涉及如何評價一個算法好壞的問題，算法分析就是評估算法所消耗資源的方法?？梢詫ν粏栴}的不同算法的代價加以比較，也可以由算法設計者根據算法分析判斷一種算法在實現時是否會遇到資源限制的問題。排序的目的之一就是方便數據的查找。在實際生活中，應根據具體情況懸著適當的算法。一般的，對于反復使用的程序，應選取時間短的算法；對于涉及數據量較大，存儲

2、空間較小的情況則應選取節(jié)約存儲空間的算法。木論文重點討論時間復雜度。時間復雜度就是一個算法所消耗的吋間。算法的效率指的是最壞情況下的算法效率。排序分為內部排序和外部排序。本課程結業(yè)論文就內部排序算法（插入排序，選擇排序，交換排序，歸并排序和基數排序）的基本思想，排序步驟和實現算法等進行介紹。本論文以較為詳細的文字說明，表格對比，例子闡述等方面加以比較和總結，通過在參加數據的規(guī)模，記錄說帶的信息量大小，對排序穩(wěn)定的要求，關鍵字的分布情況以及算法的時間復雜度和空間復雜度等方面進行比較，得出它們的優(yōu)缺點和不足，從而加深了對它們的

3、認識和了解，進而使自己在以后的學習和應用中能夠更好的運用。1?五種排序算法的實例:1.1?插入排序1.1.1.直接插入排序思路：將數組分為無序區(qū)和有序區(qū)兩個區(qū)，然后不斷將無序區(qū)的笫一個元素按大小順序插入到有序區(qū)中去，最終將所有無序區(qū)元素都移動到有序區(qū)完成排序。要點：設立哨兵，作為臨時存儲和判斷數組邊界Z用。實現：VoidTnsertSort(NodeL[],intlength){Tnti,j;//分別為有序區(qū)和無序區(qū)指針for(i=l;i

4、[O]=L[j];//存儲待排序元素While(L[0]

5、d>=l)//直到增量縮小為1{Shell(L,d);d=d/2;//縮小增量VoidShell(NodeL[],intd)Inti,j;For(i=d+l;i

6、別為有序區(qū)和無序區(qū)指針for(i=l;i

7、要點：增量的選擇以及排序最終以1為增量進行排序結束。實現：VoidshellSort(NodeL[],intd){While(d>=l)//直到增量縮小為1{Shell(L,d);d=d/2;//縮小增量VoidShell(NodeL[],intd)Inti,j;For(i=d+l;iO&&L[j]>L[O]){L[j+d]=L[j];//移動j二j-d;〃查找}L[j+d]二L[0];}1?2?選擇排序1.2.1.直接

8、選擇排序思路：將序列劃分為無序和冇序區(qū)，尋找無序區(qū)中的最小值和無序區(qū)的首元素交換，冇序區(qū)擴大一個，循環(huán)最終完成全部排序。實現：VoidSelectSort(NodeL[]){Inti,j,k;//分別為有序區(qū)，無序區(qū)，無序區(qū)最小元素指針For(i=0;i