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

馮毅宏 楊英翔 劉冬莉 何彤

摘 要：排序算法是計算機(jī)程序設(shè)計的一個重要內(nèi)容，對排序算法的分析與研究具有廣泛的應(yīng)用價值。本文介紹了常見的排序算法，并通過對比分析，對各種排序算法從算法評價角度給出了綜合評價。

關(guān)鍵詞：排序算法；內(nèi)部排序；對比分析；算法評價

排序是程序設(shè)計的常見問題，選擇合理高效的排序算法是數(shù)據(jù)處理的最重要的研究問題之一。排序算法的功能是將一個由一組數(shù)據(jù)元素或記錄組成的無序序列，重新排列成一個按關(guān)鍵字有序的序列[1]。有序序列可有效地提高記錄的查找效率。

1 排序算法分類

1.1 內(nèi)部排序

內(nèi)部排序是指待排序列完全存放在內(nèi)存中所進(jìn)行的排序過程，適合規(guī)模不太大的數(shù)據(jù)元素序列。內(nèi)部排序可分為五類： 插入排序、交換排序、選擇排序、歸并排序和分配排序。

1.2 外部排序

外部排序是指待排序的序列無法一次裝入內(nèi)存，需要在內(nèi)存和外存之間進(jìn)行多次數(shù)據(jù)交換，從而達(dá)到對序列中全部數(shù)據(jù)元素的排序。外部排序可將待排序序列分解成幾段能夠一次性裝人內(nèi)存的待排序部分，然后對每一小段采用內(nèi)部排序，再對已經(jīng)排序的各子段進(jìn)行歸并排序。即外部排序轉(zhuǎn)化為內(nèi)部排序。因此需對內(nèi)部排序進(jìn)行更深入的研究分析。

2 常見的排序算法

2.1 插入排序

插入排序每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的序列中適當(dāng)位置，使序列依然有序，直到待排序數(shù)據(jù)元素全部插入完為止。插入排序包括直接插入排序、折半插入排序和希爾排序。

（1）直接插入排序：將無序序列中的第一個數(shù)據(jù)元素依次插入到有序序列的合適位置，使有序序列仍然有序。

（2）折半插入排序：在有序序列中用折半法（二分法）查找待插入數(shù)據(jù)元素的位置。將處于有序序列中間位置數(shù)據(jù)元素的關(guān)鍵字和待排序數(shù)據(jù)元素的關(guān)鍵字比較，便把可插入的區(qū)間縮小一半，故稱為折半。折半插入排序僅減少了關(guān)鍵字間的比較次數(shù)，但數(shù)據(jù)元素的移動次數(shù)不變。

（3）希爾排序：先 取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1組。所有距離為d1的倍數(shù)的記錄放在同一組中。先在各組內(nèi)進(jìn)行直接插入排序，然后取第二個增量d2

2.2 交換排序

交換排序是指通過在數(shù)據(jù)元素之間互相交換逆序元素而進(jìn)行的排序。交換排序包括冒泡排序和快速排序。

（1）冒泡排序：通過將相鄰的數(shù)據(jù)元素進(jìn)行比較，若逆序則交換，逐步將無序序列處理成為有序序列。每一趟交換排序都會增加一個元素到有序區(qū)，整個冒泡排序過程最多需要進(jìn)行n-1趟排序。

（2）快速排序：通過一趟排序?qū)⒋判虻臄?shù)據(jù)元素分割成獨立的兩部分，其中一部分?jǐn)?shù)據(jù)元素的關(guān)鍵字均比另一部分?jǐn)?shù)據(jù)元素的關(guān)鍵字小。則可分別對這兩部分元素繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。

2.3 選擇排序

選擇排序是每一趟從待排序的數(shù)據(jù)元素中選出關(guān)鍵字最?。ɑ蜃畲螅┑囊粋€元素，插入已排序序列的最后，直到n個數(shù)據(jù)元素全部插入已排序序列中。選擇排序包括簡單選擇排序、樹型選擇排序和堆排序。

（1）簡單選擇排序：從無序的序列中選取一個關(guān)鍵字最小的數(shù)據(jù)元素存放到有序序列中指定的位置。

（2）樹型選擇排序：又稱為錦標(biāo)賽排序，是按錦標(biāo)賽思想進(jìn)行選擇排序的方法。先對n個數(shù)據(jù)元素的關(guān)鍵字進(jìn)行兩兩比較，然后在其中的（n/2）個較小者間再進(jìn)行兩兩比較，如此往復(fù)，直至選出最小關(guān)鍵字的數(shù)據(jù)元素為止。這個過程可用一棵n個結(jié)點的完全二叉樹來表示。

（3）堆排序：堆是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點的關(guān)鍵字均大于等于其孩子結(jié)點的關(guān)鍵字。這種堆中根結(jié)點（稱為堆頂）的關(guān)鍵字最小，稱之為小根堆；反之，則稱之為大根堆。堆排序的算法是：將當(dāng)前無序區(qū)調(diào)整為一個大根堆（或小根堆），選取關(guān)鍵字最大（或最?。┑亩秧斢涗?，將它和無序區(qū)中的最后一個記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個記錄區(qū)。

2.4 歸并排序

歸并排序是將兩個或兩個以上的有序序列合并成一個新的有序序列。歸并排序包括二路歸并排序和多路歸并排序。

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

（2）多路歸并排序：將多個有序序列合并成一個新的有序序列。通常用于外部排序。

2.5 分配排序

分配排序的排序過程無須比較關(guān)鍵字，而是通過分配和收集過程來實現(xiàn)排序。分配排序包括箱排序和基數(shù)排序。

（1）箱排序。

箱排序是設(shè)置若干個箱子，依次掃描待排序的數(shù)據(jù)元素R[0]，R[1]，…，R[n-1]，把關(guān)鍵字等于k的記錄全都裝入到第k個箱子里（分配），然后按序號依次將各非空的箱子首尾連接起來（收集）。

（2）基數(shù)排序

基數(shù)排序的算法是：一個邏輯關(guān)鍵字可以看成由若干個關(guān)鍵字復(fù)合而成的，可把每個排序關(guān)鍵字看成是一個d元組，即例如由關(guān)鍵字K由d個關(guān)鍵字（K0，K1，…，Kd-1）組成，排序時先按K0的值從小到大（或從大到小）將記錄分配到r個盒子中，然后依次收集這些記錄，再按K1的值分配到r個盒子中，如此反復(fù)，直到按Kd-1的值分配后收集起來的序列，便是完全排序的狀態(tài)，其中r稱為基數(shù)。基數(shù)的選擇和關(guān)鍵字的分解法因關(guān)鍵字的類型而異?；鶖?shù)排序分為最高位優(yōu)先法和最低位優(yōu)先法。

3 算法評價

3.1 穩(wěn)定性

在待排序的序列中，若存在元素值相同的記錄，經(jīng)過排序后，這些元素的相對次序不變，那么此算法為穩(wěn)定的。冒泡排序、插入排序、歸并排序和基數(shù)排序是穩(wěn)定的排序算法；選擇排序、快速排序、希爾排序、堆排序是不穩(wěn)定的排序算法。

3.2 時間復(fù)雜度

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

3.3 空間復(fù)雜度

空間性能是排序所需輔助空間大小，所有簡單排序和堆排序都是O （1）；歸并排序和基數(shù)排序所需輔助空間最多，為O（n）。

4 結(jié)論

排序算法有很多，具體情況中使用哪一種算法很重要。為了選擇合適的算法，應(yīng)順序考慮以下標(biāo)準(zhǔn)： 執(zhí)行時間 ，存儲空間，編程工作量。數(shù)據(jù)量較小時，執(zhí)行時間 和存儲空間差別不大，主要考慮編程工作量；當(dāng)數(shù)據(jù)量大時， 執(zhí)行時間為首要。相對來說，簡單排序中直接插入排序最好，快速排序最快，當(dāng)序列為正序時，直接插入排序和冒泡排序都是較好選擇。

參考文獻(xiàn)

[1] 劉冬莉， 徐立輝. 大學(xué)計算機(jī)基礎(chǔ)教程[M]. 北京：清華大學(xué)出版社， 2011.

[2] 嚴(yán)蔚敏， 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M] . 北京：清華大學(xué)出版社， 2002.

[3] 劉模群. 排序算法時間復(fù)雜度研究[J]. 軟件導(dǎo)刊， 2012（6）.

作者簡介

馮毅宏，女，講師， 主要從事非線性動力系統(tǒng)圖形化和計算機(jī)教育研究。