排序算法實驗報告

1、數(shù)據(jù)結(jié)構(gòu)實驗報告八種排序算法實驗報告一、 實驗內(nèi)容編寫關(guān)于八種排序算法的 C 語言程序，要求包含直接插入排序、希爾排序、簡單選擇排序、堆排序、冒泡排序、快速排序、歸并排序和基數(shù)排序。二、 實驗步驟各種內(nèi)部排序算法的比較：1. 八種排序算法的復(fù)雜度分析（時間與空間） 。2. 八種排序算法的 C 語言編程實現(xiàn)。3. 八種排序算法的比較，包括比較次數(shù)、移動次數(shù)。三、 穩(wěn)定性，時間復(fù)雜度和空間復(fù)雜度分析比較時間復(fù)雜度函數(shù)的情況：時間復(fù)雜度函數(shù)O(n) 的增長情況所以對 n 較大的排序記錄。 一般的選擇都是時間復(fù)雜度為方法。時間復(fù)雜度來說：(1) 平方階 (O(n2) 排序各類簡單排序 : 直接插入、直

2、接選擇和冒泡排序；(2) 線性對數(shù)階 (O(nlog2n)排序O(nlog2n)的排序快速排序、堆排序和歸并排序；(3)O(n1+ ) 排序 , 是介于 0 和1 之間的常數(shù)。希爾排序(4) 線性階 (O(n) 排序基數(shù)排序，此外還有桶、箱排序。說明：當原表有序或基本有序時， 直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)，時間復(fù)雜度可降至 O（ n）；而快速排序則相反， 當原表基本有序時， 將蛻化為冒泡排序， 時間復(fù)雜度提高為 O（n2）；原表是否有序， 對簡單選擇排序、 堆排序、歸并排序和基數(shù)排序的時間復(fù)雜度影響不大。穩(wěn)定性：排序算法的穩(wěn)定性 : 若待排序的序列中，存在多個具有相

3、同關(guān)鍵字的記錄，經(jīng)過排序， 這些記錄的相對次序保持不變， 則稱該算法是穩(wěn)定的； 若經(jīng)排序后，記錄的相對 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。穩(wěn)定性的好處： 排序算法如果是穩(wěn)定的， 那么從一個鍵上排序， 然后再從另一個鍵上排序， 第一個鍵排序的結(jié)果可以為第二個鍵排序所用。 基數(shù)排序就是這樣，先按低位排序， 逐次按高位排序， 低位相同的元素其順序再高位也相同時是不會改變的。另外，如果排序算法穩(wěn)定，可以避免多余的比較；穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序四、 設(shè)計細節(jié)排序有內(nèi)部排序和外部排序， 內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行

4、排序， 而外部排序是因排序的數(shù)據(jù)很大， 一次不能容納全部的排序記錄， 在排序過程中需要訪問外存。我們這里說說八大排序就是內(nèi)部排序。1. 插入排序 -直接插入排序（ Straight lnsertion Sort）基本思想 ：將一個記錄插入到已排序好的有序表中， 從而得到一個新，記錄數(shù)增 1 的有序表。即：先將序列的第 1 個記錄看成是一個有序的子序列，然后從第 2 個記錄逐個進行插入，直至整個序列有序為止。要點：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。直接插入排序示例：如果碰見一個和插入元素相等的， 那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列

5、出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。時效分析：時間復(fù)雜度： O（ n2）2. 插入排序 希爾排序（ Shells Sort）希爾排序是 1959 年由 D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序， 待整個序列中的記錄 “基本有序 ”時，再對全體記錄進行依次直接插入排序。操作方法：1. 選擇一個增量序列 t1，t2， ，tk，其中 titj ，tk=1；2. 按增量序列個數(shù) k，對序列進行 k 趟排序；3. 每趟排序，根據(jù)對應(yīng)的增量 ti ，將待排序列分割成若干長度為 m

6、 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。希爾排序的示例：算法的實現(xiàn)：我們簡單處理增量 序列 ：增 量序 列 d = n/2 ,n/4, n/8 .1 n 為要排序數(shù)的個數(shù)即：先將要排序的一組記錄按某個增量 d（n/2,n 為要排序數(shù)的個數(shù)）分成若干組子序列，每組中記錄的下標相差 d.對每組中全部元素進行直接插入排序， 然后再用一個較小的增量（ d/2）對它進行分組， 在每組中再進行直接插入排序。 繼續(xù)不斷縮小增量直至為 1，最后使用直接插入排序完成排序。時效分析：希爾排序時效分析很難， 關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依

7、賴于增量因子序列 d 的選取，特定情況下可以準確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。 目前還沒有人給出選取最好的增量因子序列的方法。 增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除 1 外沒有公因子，且最后一個增量因子必須為 1。希爾排序方法是一個不穩(wěn)定的排序方法。3. 選擇排序 簡單選擇排序（ Simple Selection Sort）基本思想 ：在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1 個位置的數(shù)交換；然后在剩下的數(shù)當中再找最?。ɑ蛘咦畲螅┑呐c第 2 個位置的數(shù)交換，依次類推，直到第 n-1 個元素（倒數(shù)第二個數(shù)）和第 n 個元素（最后一

8、個數(shù)）比較為止。簡單選擇排序的示例：操作方法：第一趟，從 n 個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換；第二趟，從第二個記錄開始的 n-1 個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；以此類推 .第 i 趟，則從第 i 個記錄開始的 n-i+1 個記錄中選出關(guān)鍵碼最小的記錄與第 i 個記錄交換，直到整個序列按關(guān)鍵碼有序。4. 選擇排序 堆排序（ Heap Sort）堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進?；舅枷?：堆的定義如下：具有 n 個元素的序列（k1,k2,.,kn),當且僅當滿足時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。若以一

9、維數(shù)組存儲一個堆， 則堆對應(yīng)一棵完全二叉樹， 且所有非葉結(jié)點的值均不大于 (或不小于 )其子女的值，根結(jié)點（堆頂元素）的值是最小 (或最大 )的。如：（a）大頂堆序列：（96, 83,27,38,11,09)(b)小頂堆序列：（12，36， 24，85，47， 30，53，91）初始時把要排序的 n 個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹），調(diào)整它們的存儲序， 使之成為一個堆，將堆頂元素輸出， 得到 n 個元素中最小 (或最大 )的元素，這時堆的根節(jié)點的數(shù)最?。ɑ蛘咦畲螅?。然后對前面 (n-1)個元素重新調(diào)整使之成為堆，輸出堆頂元素，得到 n 個元素中次小 (或次大 ) 的

10、元素。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有 n 個節(jié)點的有序序列。稱這個過程為堆排序。因此，實現(xiàn)堆排序需解決兩個問題：1. 如何將 n 個待排序的數(shù)建成堆；2. 輸出堆頂元素后，怎樣調(diào)整剩余 n-1 個元素，使其成為一個新堆。首先討論第二個問題：輸出堆頂元素后，對剩余 n-1 元素重新建成堆的調(diào)整過程。調(diào)整小頂堆的方法：1）設(shè)有 m 個元素的堆，輸出堆頂元素后，剩下 m-1 個元素。將堆底元素送入堆頂 （最后一個元素與堆頂進行交換） ，堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。2）將根結(jié)點與左、右子樹中較小元素的進行交換。3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的

11、根結(jié)點不滿足堆的性質(zhì)，則重復(fù)方法 （ 2）.4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點不滿足堆的性質(zhì)。則重復(fù)方法 （ 2）.5）繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結(jié)點，堆被建成。稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。如圖：再討論對 n 個元素初始建堆的過程。建堆方法：對初始序列建堆的過程， 就是一個反復(fù)進行篩選的過程。1）n 個結(jié)點的完全二叉樹， 則最后一個結(jié)點是第個結(jié)點的子樹。2）篩選從第個結(jié)點為根的子樹開始，該子樹成為堆。3）之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆，直到根結(jié)點。如圖建堆初始過程：無序序列： （49，38，65，97，76，13，

12、27，49）算法的實現(xiàn)：從算法描述來看， 堆排序需要兩個過程， 一是建立堆， 二是堆頂與堆的最后一個元素交換位置。 所以堆排序有兩個函數(shù)組成。 一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實現(xiàn)排序的函數(shù)。時效分析：設(shè)樹深度為 k，。從根到葉的篩選，元素比較次數(shù)至多 2(k-1) 次，交換記錄至多 k 次。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：而建堆時的比較次數(shù)不超過 4n 次，因此堆排序最壞情況下，時間復(fù)雜度也為： O(nlogn )。5. 交換排序 冒泡排序（ Bubble Sort）基本思想 ：在要排序的一組數(shù)中， 對當前還未排好序的范圍內(nèi)的全部數(shù)， 自上而下對相鄰的兩個數(shù)依次進行

13、比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。 即：每當兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。冒泡排序的示例：6. 交換排序 快速排序（ Quick Sort）基本思想 ：1）選擇一個基準元素 ,通常選擇第一個元素或者最后一個元素,2）通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的 元素值比基準值大。3）此時基準元素在其排好序后的正確位置4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進行排序，直到整個序列有序?？焖倥判虻氖纠海╝） 一趟排序的過程：（b） 排序的全過程：時效分析：快速排序是通常被認為在同數(shù)量級（ O(nl

14、og2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以 “三者取中法”來選取基準記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄。 快速排序是一個不穩(wěn)定的排序方法。7. 歸并排序（ Merge Sort）基本思想 ：歸并（ Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表， 即把待排序序列分為若干個子序列， 每個子序列是有序的。然后再把有序子序列合并為整體有序序列。歸并排序示例：算法的實現(xiàn)：1 個元素的表總是有序的。 所以對 n 個元素的待排序列， 每個元素可看成 1 個有序子表。對子表兩兩

15、合并生成 n/2 個子表，所得子表除最后一個子表長度可能為 1 外，其余子表長度均為2。再進行兩兩合并，直到生成 n 個元素按關(guān)鍵碼有序的表。8. 桶排序 /基數(shù)排序 (Radix Sort)基本思想 ：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序， 再按高優(yōu)先級排序。 最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前。 基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。五、 程序設(shè)計1、直接插入排序算法的實現(xiàn)2、希爾排序算法的實現(xiàn)3、簡單選擇排序算法的實現(xiàn)4、堆排序算法的實現(xiàn)5、冒泡排序算法優(yōu)化后的實

16、現(xiàn)6、快速排序算法的實現(xiàn)7、歸并排序算法的實現(xiàn)8、基數(shù)排序算法的實現(xiàn)六、 測試結(jié)果1、 直接插入排序算法的實現(xiàn)有如下結(jié)果：2、 希爾排序算法的實現(xiàn)有如下結(jié)果：3、 簡單選擇排序算法的實現(xiàn)4、 堆排序算法的實現(xiàn)5、 冒泡排序算法優(yōu)化后的實現(xiàn)6、 快速排序算法的實現(xiàn)7、 歸并排序算法的實現(xiàn)8、 基數(shù)排序算法的實現(xiàn)七、 總結(jié)反思本次對于八種排序的系統(tǒng)學(xué)習(xí)，利用圖標的記憶能夠很好的幫助學(xué)習(xí)。花了很長時間終于把排序的基礎(chǔ)學(xué)了一下，這段時間學(xué)了很多東西，總結(jié)一下：學(xué)的排序算法有：插入排序，合并排序，冒泡排序，選擇排序，希爾排序，堆排序，快速排序，基數(shù)排序。比較一下學(xué)習(xí)后的心得。我不是很清楚他們的時間復(fù)雜度

17、，也真的不知道他們到底誰快誰慢，因為書上的推導(dǎo)我確實只是小小了解， 并沒有消化。 也沒有完全理解他們的精髓， 所以又什么錯誤的還需要高手指點。1. 排序穩(wěn)定，所謂排序穩(wěn)定就是指：如果兩個數(shù)相同，對他們進行的排序結(jié)果為他們的相對順序不變。 例如 A=1,2,1,2,1這里排序之后是 A = 1,1,1,2,2穩(wěn)定就是排序后第一個 1 就是排序前的第一個1，第二個 1 就是排序前第二個1，第三個 1 就是排序前的第三個 1。同理 2 也是一樣。這里用顏色標明了。不穩(wěn)定呢就是他們的順序不應(yīng)和開始順序一致。 也就是可能會是 A=1,1,1,2,2 這樣的結(jié)果。2. 感覺誰最好，在我的印象中快速排序是最

18、好的，時間復(fù)雜度： n*log(n) ，不穩(wěn)定排序。原地排序。他的名字很棒，快速嘛。當然快了。我覺得他的思想很不錯，分治，而且還是原地排序，省去和很多的空間浪費。速度也是很快的，n*log(n) 。但是有一個軟肋就是如果已經(jīng)是排好的情況下時間復(fù)雜度就是 n*n, 不過在加入隨機的情況下這種情況也得以好轉(zhuǎn)， 而且他可以做任意的比較， 只要你能給出兩個元素的大小關(guān)系就可以了。適用范圍廣，速度快。3. 插入排序： n*n 的時間復(fù)雜度，穩(wěn)定排序，原地排序。插入排序是我學(xué)的第一個排序， 速度還是很快的， 特別是在數(shù)組已排好了之后， 用它的思想來插入一個數(shù)據(jù)，效率是很高的。因為不用全部排。他的數(shù)據(jù)交換也

19、很少，只是數(shù)據(jù)后移，然后放入要插入的數(shù)據(jù)。（這里不是指調(diào)用插入排序，而是用它的思想） 。我覺得，在數(shù)據(jù)大部分都排好了， 用插入排序會給你帶來很大的方便。 數(shù)據(jù)的移動和交換都很少。4. 冒泡排序， n*n 的時間復(fù)雜度，穩(wěn)定排序，原地排序。冒泡排序的思想很不錯，一個一個比較，把小的上移，依次確定當前最小元素。因為他簡單，穩(wěn)定排序，而且好實現(xiàn)， 所以用處也是比較多的。 還有一點就是加上哨兵之后他可以提前退出。5. 選擇排序， n*n 的時間復(fù)雜度， 穩(wěn)定排序，原地排序。選擇排序就是冒泡的基本思想，從小的定位，一個一個選擇，直到選擇結(jié)束。他和插入排序是一個相反的過程， 插入是確定一個元素的位置， 而

20、選擇是確定這個位置的元素。 他的好處就是每次只選擇確定的元素， 不會對很多數(shù)據(jù)進行交換。 所以在數(shù)據(jù)交換量上應(yīng)該比冒泡小。6. 插入排序，選擇排序，冒泡排序的比較，他們的時間復(fù)雜度都是 n*n 。我覺得他們的效率也是差不多的， 我個人喜歡冒泡一些， 因為要用它的時候數(shù)據(jù)多半不多，而且可以提前的返回已經(jīng)排序好的數(shù)組。 而其他兩個排序就算已經(jīng)排好了，他也要做全部的掃描。在數(shù)據(jù)的交換上，冒泡的確比他們都多。舉例說明插入一個數(shù)據(jù)在末尾后排序，冒泡只要一次就能搞定，而選擇和插入都必須要 n*n 的復(fù)雜度才能搞定。7. 合并排序： n*log(n) 的時間復(fù)雜度， 穩(wěn)定排序，非原地排序。他的思想是分治，先

21、分成小的部分，排好部分之后合并，因為我們另外申請的空間，在合并的時候效率是 0(n) 的。速度很快。貌似他的上限是 n*log(n) ，所以如果說是比較的次數(shù)的話，他比快速排序要少一些。 對任意的數(shù)組都能有效地在 n*log(n) 排好序。但是因為他是非原地排序， 所以雖然他很快， 但是貌似他的人氣沒有快速排序高。8. 堆排序： n*log(n) 的時間復(fù)雜度， 非穩(wěn)定排序，原地排序。他的思想是利用的堆這種數(shù)據(jù)結(jié)構(gòu)， 堆可以看成一個完全二叉樹， 所以在排序中比較的次數(shù)可以做到很少。加上他也是原地排序，不需要申請額外的空間，效率也不錯?？墒撬乃枷敫杏X比快速難掌握一些。 還有就是在已經(jīng)排好序的基

22、礎(chǔ)上添加一個數(shù)據(jù)再排序，他的交換次數(shù)和比較次數(shù)一點都不會減少。 雖然堆排序在使用的中沒有快速排序廣泛， 但是他的數(shù)據(jù)結(jié)構(gòu)和思想真的很不錯， 而且用它來實現(xiàn)優(yōu)先隊列，效率沒得說。堆，還是要好好學(xué)習(xí)掌握的。9. 希爾排序： n*log(n)的時間復(fù)雜度 ( 這里是錯誤的，應(yīng)該是nlamda(1 lamda 2), lamda 和每次步長選擇有關(guān)。 ) ， 非穩(wěn)定排序，原地排序。主要思想是分治，不過他的分治和合并排序的分治不一樣， 他是按步長來分組的， 而不是想合并那樣左一半右一半。 開始步長為整個的長度的一半。 分成 nLen/2 個組，然后每組排序。接個步長減為原來的一半在分組排序，直到步長為 1，排序之后希爾排序就完成了。 這個思路很好， 據(jù)說是插入排序的升級版， 所以在實現(xiàn)每組排序的時候我故意用了插入排序。 我覺得他是一個特別好的排序方法了。 他的缺點就是兩個數(shù)可能比較多次， 因為兩個數(shù)據(jù)會多次分不過他們不會出現(xiàn)數(shù)據(jù)的交換。效率也是很高的。10. 快速排序，堆排序，合并排序，希爾排序的比較，他們的時間復(fù)雜的都是 n*log(n) ，我認為在使用上快速排序最廣泛，他原地排序，雖然不穩(wěn)定，可是很多情況下排序根本就不在意他是否穩(wěn)定。 他的比較次數(shù)是比較小的， 因為他把數(shù)據(jù)分成了大和小的兩部分。 每次都確定了一個數(shù)的位置