程序設(shè)計排序算法分析

1、<p>　　程序設(shè)計排序算法分析</p><p>　　摘 要：排序算法是計算機程序設(shè)計的一個重要內(nèi)容，對排序算法的分析與研究具有廣泛的應(yīng)用價值。本文介紹了常見的排序算法，并通過對比分析，對各種排序算法從算法評價角度給出了綜合評價。 </p><p>　　關(guān)鍵詞：排序算法；內(nèi)部排序；對比分析；算法評價 </p><p>　　排序是程序設(shè)計的常見問題，選擇合理

2、高效的排序算法是數(shù)據(jù)處理的最重要的研究問題之一。排序算法的功能是將一個由一組數(shù)據(jù)元素或記錄組成的無序序列，重新排列成一個按關(guān)鍵字有序的序列[1]。有序序列可有效地提高記錄的查找效率。 </p><p><b>　　1 排序算法分類 </b></p><p><b>　　1.1 內(nèi)部排序 </b></p><p>　　內(nèi)部排

3、序是指待排序列完全存放在內(nèi)存中所進行的排序過程，適合規(guī)模不太大的數(shù)據(jù)元素序列。內(nèi)部排序可分為五類： 插入排序、交換排序、選擇排序、歸并排序和分配排序。 </p><p><b>　　1.2 外部排序 </b></p><p>　　外部排序是指待排序的序列無法一次裝入內(nèi)存，需要在內(nèi)存和外存之間進行多次數(shù)據(jù)交換，從而達到對序列中全部數(shù)據(jù)元素的排序。外部排序可將待排序序列分

4、解成幾段能夠一次性裝人內(nèi)存的待排序部分，然后對每一小段采用內(nèi)部排序，再對已經(jīng)排序的各子段進行歸并排序。即外部排序轉(zhuǎn)化為內(nèi)部排序。因此需對內(nèi)部排序進行更深入的研究分析。 </p><p>　　2 常見的排序算法 </p><p><b>　　2.1 插入排序 </b></p><p>　　插入排序每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的

5、序列中適當位置，使序列依然有序，直到待排序數(shù)據(jù)元素全部插入完為止。插入排序包括直接插入排序、折半插入排序和希爾排序。 </p><p>　?。?）直接插入排序：將無序序列中的第一個數(shù)據(jù)元素依次插入到有序序列的合適位置，使有序序列仍然有序。 </p><p>　?。?）折半插入排序：在有序序列中用折半法（二分法）查找待插入數(shù)據(jù)元素的位置。將處于有序序列中間位置數(shù)據(jù)元素的關(guān)鍵字和待排序數(shù)據(jù)元素

6、的關(guān)鍵字比較，便把可插入的區(qū)間縮小一半，故稱為折半。折半插入排序僅減少了關(guān)鍵字間的比較次數(shù)，但數(shù)據(jù)元素的移動次數(shù)不變。 </p><p>　?。?）希爾排序：先 取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1組。所有距離為d1的倍數(shù)的記錄放在同一組中。先在各組內(nèi)進行直接插入排序，然后取第二個增量d2<d1重復(fù)上述的分組和排序，直到所取的增量dt=1，即所有記錄放在同一組中進行直接插入排序為止

7、。 </p><p><b>　　2.2 交換排序 </b></p><p>　　交換排序是指通過在數(shù)據(jù)元素之間互相交換逆序元素而進行的排序。交換排序包括冒泡排序和快速排序。 </p><p>　?。?）冒泡排序：通過將相鄰的數(shù)據(jù)元素進行比較，若逆序則交換，逐步將無序序列處理成為有序序列。每一趟交換排序都會增加一個元素到有序區(qū)，整個冒泡排序過程

8、最多需要進行n-1趟排序。 </p><p>　　（2）快速排序：通過一趟排序?qū)⒋判虻臄?shù)據(jù)元素分割成獨立的兩部分，其中一部分數(shù)據(jù)元素的關(guān)鍵字均比另一部分數(shù)據(jù)元素的關(guān)鍵字小。則可分別對這兩部分元素繼續(xù)進行排序，以達到整個序列有序。 </p><p><b>　　2.3 選擇排序 </b></p><p>　　選擇排序是每一趟從待排序的數(shù)據(jù)元素中

9、選出關(guān)鍵字最?。ɑ蜃畲螅┑囊粋€元素，插入已排序序列的最后，直到n個數(shù)據(jù)元素全部插入已排序序列中。選擇排序包括簡單選擇排序、樹型選擇排序和堆排序。 </p><p>　?。?）簡單選擇排序：從無序的序列中選取一個關(guān)鍵字最小的數(shù)據(jù)元素存放到有序序列中指定的位置。 </p><p>　　（2）樹型選擇排序：又稱為錦標賽排序，是按錦標賽思想進行選擇排序的方法。先對n個數(shù)據(jù)元素的關(guān)鍵字進行兩兩比較，

10、然后在其中的（n/2）個較小者間再進行兩兩比較，如此往復(fù)，直至選出最小關(guān)鍵字的數(shù)據(jù)元素為止。這個過程可用一棵n個結(jié)點的完全二叉樹來表示。 </p><p>　　（3）堆排序：堆是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，稱之為小根堆；反之，則稱之為大根堆。堆排序的算法是：將當前無序區(qū)調(diào)整為一個大根堆（或小根堆），選取關(guān)鍵字最大（或最小

11、）的堆頂記錄，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴大到整個記錄區(qū)。 </p><p><b>　　2.4 歸并排序 </b></p><p>　　歸并排序是將兩個或兩個以上的有序序列合并成一個新的有序序列。歸并排序包括二路歸并排序和多路歸并排序。 </p><p>　?。?）二

12、路歸并排序：將兩個有序序列合并成一個新的有序序列。先從兩個有序序列中分別取第一個數(shù)據(jù)元素比較，關(guān)鍵字?。ɑ虼螅┑臄?shù)據(jù)元素排入新的有序序列，同時在對應(yīng)原序列中刪除該數(shù)據(jù)元素；然后再從兩個有序序列中分別取第一個數(shù)據(jù)元素比較，如此循環(huán)；當有一個序列為空時，則直接將另一個序列的數(shù)據(jù)元素依次取出即可。 </p><p>　　（2）多路歸并排序：將多個有序序列合并成一個新的有序序列。通常用于外部排序。 </p>

13、<p><b>　　2.5 分配排序 </b></p><p>　　分配排序的排序過程無須比較關(guān)鍵字，而是通過分配和收集過程來實現(xiàn)排序。分配排序包括箱排序和基數(shù)排序。 </p><p><b>　?。?）箱排序。 </b></p><p>　　箱排序是設(shè)置若干個箱子，依次掃描待排序的數(shù)據(jù)元素R[0]，R[1]，

14、…，R[n-1]，把關(guān)鍵字等于k的記錄全都裝入到第k個箱子里（分配），然后按序號依次將各非空的箱子首尾連接起來（收集）。 </p><p><b>　?。?）基數(shù)排序 </b></p><p>　　基數(shù)排序的算法是：一個邏輯關(guān)鍵字可以看成由若干個關(guān)鍵字復(fù)合而成的，可把每個排序關(guān)鍵字看成是一個d元組，即例如由關(guān)鍵字K由d個關(guān)鍵字（K0，K1，…，Kd-1）組成，排序時先

15、按K0的值從小到大（或從大到小）將記錄分配到r個盒子中，然后依次收集這些記錄，再按K1的值分配到r個盒子中，如此反復(fù)，直到按Kd-1的值分配后收集起來的序列，便是完全排序的狀態(tài)，其中r稱為基數(shù)?；鶖?shù)的選擇和關(guān)鍵字的分解法因關(guān)鍵字的類型而異?；鶖?shù)排序分為最高位優(yōu)先法和最低位優(yōu)先法。 </p><p><b>　　3 算法評價 </b></p><p><b>

16、　　3.1 穩(wěn)定性 </b></p><p>　　在待排序的序列中，若存在元素值相同的記錄，經(jīng)過排序后，這些元素的相對次序不變，那么此算法為穩(wěn)定的。冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法；選擇排序、快速排序、希爾排序、堆排序是不穩(wěn)定的排序算法。 </p><p>　　3.2 時間復(fù)雜度 </p><p>　　時間復(fù)雜度是指執(zhí)行算法所需要的

17、計算工作量[3]。按平均情況下時間復(fù)雜度將排序分為四類：（1） 平方階（O（n2））排序：一般稱為簡單排序，如冒泡排序、簡單選擇排序和直接插入排序。（2） 線性對數(shù)階O（nlgn）排序：如快速排序、歸并排序和堆排序。（3） O（n1+￡）階排序：￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序。（4）線性階（O（n））排序：如箱排序和基數(shù)排序。 </p><p>　　3.3 空間復(fù)雜度 </p

18、><p>　　空間性能是排序所需輔助空間大小，所有簡單排序和堆排序都是O （1）；歸并排序和基數(shù)排序所需輔助空間最多，為O（n）。 </p><p><b>　　4 結(jié)論 </b></p><p>　　排序算法有很多，具體情況中使用哪一種算法很重要。為了選擇合適的算法，應(yīng)順序考慮以下標準： 執(zhí)行時間 ，存儲空間，編程工作量。數(shù)據(jù)量較小時，執(zhí)行時間

19、和存儲空間差別不大，主要考慮編程工作量；當數(shù)據(jù)量大時， 執(zhí)行時間為首要。相對來說，簡單排序中直接插入排序最好，快速排序最快，當序列為正序時，直接插入排序和冒泡排序都是較好選擇。 </p><p><b>　　參考文獻 </b></p><p>　　[1] 劉冬莉， 徐立輝. 大學計算機基礎(chǔ)教程[M]. 北京：清華大學出版社， 2011. </p><

20、;p>　　[2] 嚴蔚敏， 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M] . 北京：清華大學出版社， 2002. </p><p>　　[3] 劉模群. 排序算法時間復(fù)雜度研究[J]. 軟件導(dǎo)刊， 2012（6）. </p><p><b>　　作者簡介 </b></p><p>　　馮毅宏，女，講師， 主要從事非線性動力系統(tǒng)圖形化和計算機教育研