排序算法學習報告

1、排序算法學習報告一、 學習內(nèi)容所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增（或遞減）次序排列起來。當待排序記錄的關(guān)鍵字都不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的 相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生改變，則稱這 種排序方法是不穩(wěn)定的。要注意的是，排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有 一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。常見的排序算法2. 1插入排序插入排序是這樣實現(xiàn)的：首先新建一個空列表，用于

2、保存已排序的有序數(shù)列（我們稱之為有序列表）O從原數(shù)列中取出一個數(shù)，將其插入有序列表中，使其仍舊保持有序狀態(tài)。重復2號步驟，直至原數(shù)列 為空。插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現(xiàn)。它借助了逐步擴大成果的思想，使有序列表的長度逐漸增加，直至其長度等于原列表的長度。【示例】：初始關(guān)鍵字4938 65 97 76 13 27 49J=2 (38)J=3 (65)J=4 (97)J=5 (76)J=6(13)J=7 (27)J=8 (49)3838383813132713 2765977613274965977613274965977613274965769713274949657

3、6972749494949493865 76 9749493838 49 49 65 76 972.2冒泡排序冒泡排序是這樣實現(xiàn)的：首先將所有待排序的數(shù)字放入工作列表中。從列表的第一個數(shù)字到倒數(shù)第二個數(shù)字，逐個檢查：若某一位上的數(shù)字大于他的下一位，則將它與它的 下一位交換。重復2號步驟，直至再也不能交換。冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現(xiàn)的算法【示例】：4913131313131313384927272727272765384938383838389765384949494949769765494949494913769765656565652727769

4、77676767649494976979797972. 3選擇排序選擇排序是這樣實現(xiàn)的：設(shè)數(shù)組內(nèi)存放了 n個待排數(shù)字，數(shù)組下標從1開始，到n結(jié)束。i=l從數(shù)組的第i個元素開始到第n個元素，尋找最小的元素將上一步找到的最小元素和第i位元素交換。如果i二n -1算法結(jié)束，否則回到第3步【示例】：初始關(guān)鍵字49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后13 27 38 97 76 49 65 49第四趟排序后13 27 38 49 49 97 65 76第五趟排序后13

5、2738 49 4997 97 76第六趟排序后132738 49 497676 97第七趟排序后132738 49 497676 97最后排序結(jié)果132738 49 497676 972. 4快速排序基本思想：在當前無序區(qū)RE1.H中任取一個數(shù)據(jù)元素作為比較的基準（不妨記為X）,用此 基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：Rl1-1和RI+1H,且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元素，而基準X則位于最終排序的位置上，即 Rl. . 1-1 X. KeyW RI+1.H （1 I H），當 Rl. . 1-1和 RI+1. .H 均非空時

6、，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止?！臼纠浚撼跏缄P(guān)鍵字4938 65 97 76 13 27 49第一次交換后27 38 65 97 76 1349 49第二次交換后27 38 49 97 76 136549 J向左掃描，位置不變，第三次交換后27 3813 97 76 49 65 49 I向右掃描，位置不變，第四次交換后27 3813 49 76 97 65 49 J 向左掃描27 38 13 49 76 97 65 49（一次劃分過程） 初始關(guān)鍵字49 38 65 97 76 13 27 4965 49 -趟排序之后27 38 13 49 76 97

7、二趟排序之后13 27 38 49 4965 7697 三趟排序之后13 27 38 49 4965 76 97最后的排序結(jié)果13 27 38 49 49 65 76 972. 5堆排序基本思想：堆排序是一樹形選擇排序，在排序過程中，將RC1.N看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。堆的定義：N個元素的序列KI, K2, K3,，Kn.稱為堆，當且僅當該序列滿足特性：Ki K2i Ki K2i+1 （1 I N/2）堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。例如序列10, 15,

8、56, 25, 30, 70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。排序過程：堆排序正是利用小根堆（或大根堆）來選取當前無序區(qū)中關(guān)鍵字?。ɑ蜃畲螅┑挠涗泴崿F(xiàn)排序的。我們不妨 利用大根堆來排序。每一趟排序的基本操作是：將當前無序區(qū)調(diào)整為一個大根堆，選取關(guān)鍵字最大的堆 頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直 接選擇排序相反，有序區(qū)是在原記錄區(qū) 的尾部形成并逐步向前擴大到整個記錄區(qū)。2. 6希爾排序希爾(Shell)排序的基本思想是：先取

9、一個小于n的整數(shù)di作為第一個增量把文件的全部記錄 分成di 個組。所有距離為di的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取得第二 個增量d2dl重復上述的分組和排序，直至所取的增量di=l,即所有記錄放在同一組中進行直接插入 排序為止。該方法實質(zhì)上是一種分組插入方法。一般取dl= n/2, di+1二di/2。如果結(jié)果為偶數(shù)，貝U加1,保證di為奇數(shù)。2. 7歸并排序歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。初始時，把含有n個結(jié)點的待排序序 列看作由n個長度都為1的有序子表組成，將它們依次兩兩歸并得到長度為2的若干有序子表，再對它 們兩兩合并。直到得到長

10、度為n的有序表，排序結(jié)束。歸并排序是一種穩(wěn)定的排序，可用順序存儲結(jié)構(gòu)，也易于在鏈表上實現(xiàn)，對長度為n的文件，需進行l(wèi)og2n趟二路歸并，每趟歸并的時間為0(n)故其時間復雜度無論是在最好情況下還是在 最壞情況下均是O(nl og2 n)。歸并排序需要一個輔助向量來暫存兩個有序子文件歸并的結(jié)果，故其輔 助空間復雜度為0( n),顯然它不是就地排序。3常見排序算法比較序號排序類別時間復雜度空間復雜度穩(wěn)定1插入排序0( n2)1V2希爾排序0( n2)1X3冒泡排序0( n2)1V4選擇排序0( n2)1X5快速排序0(Nlog n)0(log n)X6堆排序0(Nlog n)1X7歸并排序0(Nl

11、og n)0(n)V穩(wěn)定性分析首先，排序算法的穩(wěn)定性大家應該都知道，通俗地講就是能保證排序前2個相等的數(shù)其在序列的前后位置順序和排序后它們兩個的前后位置順序相同。在簡單形式化一下，如果Ai二Aj, Ai原來在位置前，排序后Ai還是要在A j位置前。其次，說一下穩(wěn)定性的好處。排序算法如果是穩(wěn)定的，那么從一個鍵上排序，然后再從另一個鍵上排 序，第一個鍵排序的結(jié)果可以為第二個鍵排序所用?；鶖?shù)排序就是這樣，先按低位排序，逐次按高位排 序，低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩(wěn)定，對基于比較的排 序算法而言，元素交換的次數(shù)可能會少一些(個人感覺，沒有證實)o回到主題，現(xiàn)在分

12、析一下常見的排序算法的穩(wěn)定性，每個都給出簡單的理由。冒泡排序冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交 換一下的； 如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所 以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。(2) 選擇排序選擇排序是給每個位置選擇當前元素最小的，里面給第二個元素選擇第二小的，依次類推，直到第 因為只剩下它一個最大的元素了。那么，在一趟選擇, 現(xiàn)在一個和當前元素相等的元素后面，比如給第一個位置選擇最小

13、的，在剩余元素n-1個元素，第n個元素不用選擇了，如果當前元素比一個元素小，而該小的元素又出那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9,我們知道第一遍選擇第1個元素5會和2交換，那么原序列中2個5的相對前后順序就被破壞了，所以選擇排序不是一個穩(wěn)定的排序算法。(3) 插入排序插入排序是在一個己經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個元素。當然，岡寸開始這個有 序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入 的元素和已經(jīng)有 序的最大者開始比起，如果比它大則直接插入在其后面，否則一直往前找直到找到它該插入的位置。如 果碰見一個和插入元素相等

14、的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的 前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。(4) 快速排序快速排序有兩個方向，左邊的i下標一直往右走，當ai acenter_index。如果 i 和 j 都走不動了，i二 j,交換 ai和 aj,重復上面的過程，直到ij。交換aj和aLcenter_index,完成一趟快速排序。在中樞元素和aj交換 的時候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列為5334389 10 11現(xiàn)在中樞元素5和3 （第5個元素，下標從1開始計）交換就會把元素3的穩(wěn)定性打亂，所以快速排序是 一個不穩(wěn)定的排

15、序算法，不穩(wěn)定發(fā)生在中樞元素和aj交換的時刻。（5）歸并排序歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素（認為直接有序）或者2個序列（1次比較和交換），然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。可以發(fā)現(xiàn)，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也 沒有人故意交換，這不會破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是是否受到破壞？沒 有，合并過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素保存在結(jié)果序列 的前面，這樣就保證了穩(wěn)定性。所以，歸并排序也是穩(wěn)定的排序算法。希爾排序（shell）希爾排序是按照

16、不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入 排序的兀素個數(shù)很少，速度很快；當兀素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺?所以，希爾排序的時間復雜度會比o（nA2）好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的 元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。堆排序我們知道堆的結(jié)構(gòu)是節(jié)點i的孩子為2*i和2*i+l節(jié)點，大頂堆要求父節(jié)點大于等于其2個子節(jié) 點，小頂堆要求父節(jié)點小于等于其2個子節(jié)點。在一個長為n的序列，堆排序的過程是從第n/2開始

17、和 其子節(jié)點共3個值選擇最大（大頂堆）或者最?。ㄐ№敹眩?這3個元素之間的選擇當然不會破壞穩(wěn)定性。 但當為n /2-1, n /2-2,1這些個父節(jié)點選擇元素時，就會破壞穩(wěn)定性。有可能第n/2個父節(jié)點交 換把后面一個元素交換過去了，而第n/2-1個父節(jié)點把后面一個相同的元素沒有交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。綜上，得出結(jié)論：選擇排序、快速排序、希爾排序、堆排序不是穩(wěn)定的排序算法，而冒泡排序、插入排 序、歸并排序是穩(wěn)定的排序算法。二、心得體會剛接觸到算法這門課的時候，對算法沒什么具體的概念，總感覺學習這門課和之前的兩門程序設(shè)計 課程應該沒什么區(qū)別

18、，無非就是編程而已，但慢慢的我發(fā)現(xiàn)，算法不止是那么簡 單。Pascal語言的創(chuàng)始 人N. Wirth用這樣一個公式來總結(jié)算法的地位:算法+數(shù)據(jù)結(jié)構(gòu)二程序通過上面這個被廣大程序員普遍認同的公式可以看出，算法在程序設(shè)計中所占的重要位 置，算法是 程序的靈魂是完全正確的。一般的程序設(shè)計方法也就是編程步驟主要有以下的幾個方面：分析問題、設(shè)計算法、編 寫程序和調(diào) 試程序。其中設(shè)計算法作為整個程序調(diào)試的基礎(chǔ)，只有先設(shè)計出巧妙的算法思想，才能保證在之后的程 序能高效的執(zhí)行，編寫代碼只不過是用某種語言來實現(xiàn)算法的一個具體 表現(xiàn)形式而己。就好比排序算 法，其實我們已經(jīng)學過好幾種排序的算法，之前一直沒怎么注意它們的區(qū)別，要用到排序的時候想到哪 個或者哪個比較熟手就用那個，經(jīng)過這次的整理、比較及分析我對這幾個排序算法有了更深入的了解及 新的看法，同時自己也稍作了總結(jié)：插入、冒泡排序的速度較慢，但參加排序的序列局