五種排序算法的分析與比較

1、五種排序算法的分析與比較廣東醫(yī)學(xué)院 醫(yī)學(xué)信息專業(yè) 郭慧玲摘要：排序算法是計(jì)算機(jī)程序設(shè)計(jì)廣泛使用的解決問題的方法,研究排序算法具有重要的理論意義和廣泛的應(yīng)用價(jià)值。文章通過描述冒泡、選擇、插入、歸并和快速5種排序算法,總結(jié)了它們的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。通過實(shí)驗(yàn)驗(yàn)證了5種排序算法在隨機(jī)、正序和逆序3種情況下的性能,指出排序算法的適用原則,以供在不同條件下選擇適合的排序算法借鑒。關(guān)鍵詞：冒泡排序;選擇排序;插入排序;歸并排序;快速排序。排序是計(jì)算機(jī)科學(xué)中基本的研究課題之一,其目的是方便記錄的查找、插入和刪除。 隨著計(jì)算機(jī)的發(fā)展與應(yīng)用領(lǐng)域的越來越廣,基于計(jì)算機(jī)硬件的速度和存儲空間的有限性,如何

2、提高計(jì)算機(jī)速度并節(jié)省存儲空間一直成為軟件設(shè)計(jì)人員的努力方向。其中,排序算法已成為程序設(shè)計(jì)人員考慮的因素之一1，排序算法選擇得當(dāng)與否直接影響程序的執(zhí)行效率和內(nèi)外存儲空間的占用量,甚至影響整個(gè)軟件的綜合性能。排序操作2，3,就是將一組數(shù)據(jù)記錄的任意序列,重新排列成一個(gè)按關(guān)鍵字有序的序列。而所謂排序的穩(wěn)定性4是指如果在排序的序列中，存在前后相同的兩個(gè)元素，排序前和排序后他們的相對位置不發(fā)生變化。1算法與特性1.1冒泡排序1.1.1冒泡排序的基本思想冒泡排序的基本思想是5,6:首先將第1個(gè)記錄的關(guān)鍵字和第2個(gè)記錄的關(guān)鍵字進(jìn)行比較,若為逆序,則將2個(gè)記錄交換,然后比較第2個(gè)和第3個(gè)記錄的關(guān)鍵字,依次類推

3、,直至-1個(gè)記錄和第個(gè)記錄的關(guān)鍵字進(jìn)行過比較為止。然后再按照上述過程進(jìn)行下一次排序,直至整個(gè)序列有序?yàn)橹埂?.1.2冒泡排序的特性容易判斷冒泡排序是穩(wěn)定的?？梢苑治龀鏊男?在最好情況下,只需通過-1次比較,不需要移動關(guān)鍵字,即時(shí)間復(fù)雜度為()(即正序);在最壞情況下是初始序列為逆序,則需要進(jìn)行-1次排序,需進(jìn)行(-1)/2次比較,因此在最壞情況下時(shí)間復(fù)雜度為(2),附加存儲空間為(1)。1.2選擇排序1.2.1選擇排序的基本思想選擇排序的基本思想是5,6:每一次從待排序的記錄中選出關(guān)鍵字最小的記錄,順序放在已排好序的文件的最后,直到全部記錄排序完畢.常用的選擇排序方法有直接選擇排序和堆排序

4、,考慮到簡單和易理解,這里討論直接選擇排序。直接選擇排序的基本思想是個(gè)記錄的文件的直接排序可經(jīng)過-1次直接選擇排序得到有序結(jié)果。1.2.2選擇排序的特性容易得出選擇排序是不穩(wěn)定的。在直接選擇排序過程中所需進(jìn)行記錄移動的操作次數(shù)最少為0,最大值為3(-1)。然而,無論記錄的初始排序如何,所需進(jìn)行的關(guān)鍵字間的比較次數(shù)相同,均為(-1)/2,時(shí)間復(fù)雜度為(2),附加存儲空間為(1)。1.3插入排序1.3.1插入排序的基本思想插入排序的基本思想是5,6:每次將1個(gè)待排序的記錄按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中適當(dāng)?shù)奈恢?直到全部記錄插入完成為止。插入排序分直接插入排序、折半插入排序和希爾排序

5、3類?？紤]到簡單、易理解的因素,這里討論直接插入排序,其基本思想是:初始時(shí)0自成一個(gè)有序區(qū),無序區(qū)為1,-1,從=1至=-1為止,依次將插入到當(dāng)前的有序區(qū)中,生成含個(gè)記錄的有序區(qū)。容易得出插入排序是穩(wěn)定的。1.3.2插入排序的特性當(dāng)待排序文件為正序時(shí),所需進(jìn)行的關(guān)鍵字間比較的次數(shù)達(dá)最小值-1,記錄不需要移動;反之,逆序時(shí)比較次數(shù)達(dá)最大值(+2)(-1)/2,移動次數(shù)為(+4)(-1)/2,因此,其時(shí)間復(fù)雜度為(2),附加存儲空間為(1)。1.4歸并排序1.4.1歸并排序的基本思想歸并排序的基本思想是7,8:采用分治策略,將待排序文件分成大小大致相同的2個(gè)子集合,分別對2個(gè)子集合進(jìn)行排序,最終將

6、排好序的子集合并成所要求的排好序的集合。假設(shè)初始序列含有個(gè)記錄,則可以將每個(gè)記錄看成是長度為1的子序列,然后兩兩歸并,得到對/2 個(gè)長度為2或1的有序子序列;再兩兩歸并,如此重復(fù),直至得到1個(gè)長度為的有序序列為止。1.4.2歸并排序的特性容易得出歸并排序穩(wěn)定。歸并排序算法對個(gè)待排序記錄進(jìn)行排序,在最壞的情況下所需的計(jì)算時(shí)間()滿足: 1,()=(1); otherwise,()=()。附加存儲空間為()。1.5快速排序1.5.1快速排序的基本思想快速排序的基本思想是7,9:具體過程如下,假設(shè)當(dāng)前待排序序列為low, ,high,排序過程分為分解、求解和合并3個(gè)步驟:分解，在low, ,high

7、中任選一個(gè)記錄作為基準(zhǔn)(base),以此基準(zhǔn)將當(dāng)前待排序序列分為左、右2個(gè)子區(qū)間,前者為low, ,base-1,均小于基準(zhǔn),后者為base+1, ,high,均大于基準(zhǔn),基準(zhǔn)則處于正確的位置上;求解，通過遞歸調(diào)用快速排序?qū)ψ?、?個(gè)子區(qū)間進(jìn)行快速排序;合并，當(dāng)求解中的2個(gè)遞歸調(diào)用結(jié)束時(shí),左、右2個(gè)子區(qū)間已有序,即完成排序。 需附加存儲空間為(log2).容易得出快速排序不穩(wěn)定。1.5.2快速排序的特性根據(jù)對此排序的描述,可以分2種情況討論:1)當(dāng)待排序序列有序(序列按正序排列)時(shí),每次劃分只得到1個(gè)比上一次少1個(gè)記錄的子序列。這樣,必須經(jīng)過-1次才能把所有記錄定位,而且第次需要-次比較才能找

8、到第個(gè)記錄的正確位置,故總的比較次數(shù)達(dá)到1/2*(-1)=(2)。2)當(dāng)排序序列是隨機(jī)序列時(shí),且()是對個(gè)記錄的序列進(jìn)行排序所需的時(shí)間,每次對1個(gè)記錄正確定位后,正好把序列劃分為長度相等的2個(gè)子序列,此時(shí)()滿足1,()=(1); otherwise, ()=()。2性能評價(jià)2.1實(shí)驗(yàn)與結(jié)果為了比較各種排序算法的性能,我們使用一臺桌面電腦，在6.0環(huán)境下,用語言編寫程序,調(diào)用隨機(jī)函數(shù)、時(shí)間函數(shù)來統(tǒng)計(jì)輸入規(guī)模不同和排序不同的元素時(shí)五種排序算法的用時(shí)情況。以下實(shí)驗(yàn)結(jié)果引用于10：五種排序算法的性能分析由表1可知:當(dāng)輸入規(guī)模為10 000時(shí),5種排序算法的用時(shí)情況差不多,但隨著輸入規(guī)模的增大,快速排

9、序算法的優(yōu)勢就體現(xiàn)出來,其次是歸并排序,最差的是選擇排序,插入排序略優(yōu)于冒泡排序。由表2可知:當(dāng)輸入序列是正序時(shí),插入排序算法最佳,其次是歸并排序,快速排序略優(yōu)于冒泡排序,最差的是選擇排序。由表3可知:當(dāng)輸入序列是逆序時(shí),歸并排序算法是最理想的,最壞的是選擇排序;輸入規(guī)模在8 000個(gè)記錄范圍內(nèi)時(shí),插入排序和快速排序差不多,隨著輸入規(guī)模的增大, 快速排序比插入排序耗時(shí)更少;輸入規(guī)模在4 000個(gè)記錄范圍內(nèi)時(shí),冒泡排序和選擇排序幾乎一樣,差別極其微小,隨著規(guī)模增大,冒泡排序優(yōu)于選擇排序。2.2算法性能評價(jià)評價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有3條11:執(zhí)行時(shí)間、所需的輔助空間以及算法的穩(wěn)定性。算法本身的復(fù)

10、雜程度,即空間復(fù)雜度和時(shí)間復(fù)雜度。如果所需的輔助空間并不依賴于問題的規(guī)模,即輔助空間是(1),稱之為就地排序;非就地排序一般要求的輔助空間為()。然而,時(shí)間復(fù)雜度12取決于算法本身涉及的記錄之間的比較次數(shù)和交換次數(shù)。總結(jié)排序算法比較（表4）排序方法平均時(shí)間復(fù)雜度最壞情況空間復(fù)雜度穩(wěn)定性冒泡排序O(n2)O(n2)O(1)穩(wěn)定選擇排序O(n2)O(n2)O(1)不穩(wěn)定插入排序O(n2)O(n2)O(1)穩(wěn)定歸并排序O(nlogn)O(nlogn)O(n)穩(wěn)定快速排序O(nlogn)O(n2)(log2)不穩(wěn)定綜合比較上述討論的幾種內(nèi)部排序算法,可得到如表4所示的結(jié)論。根據(jù)表4,可以將5種排序算法

11、按照平均時(shí)間分為2類:冒泡排序、選擇排序、插入排序其時(shí)間復(fù)雜度為(2),即平方階排序;歸并排序、快速排序其時(shí)間復(fù)雜度為(log),即線性對數(shù)階排序。從平均時(shí)間性能而言,快速排序和歸并排序優(yōu)越于其他3種排序,所需時(shí)間最省,但在最壞情況下,快速排序則不如歸并排序。在輸入規(guī)模較大時(shí),快速排序比較有優(yōu)勢,但當(dāng)輸入規(guī)模不是很大時(shí),5種排序算法的耗時(shí)相差無幾。就空間復(fù)雜度而言,快速和歸并排序的輔助空間開銷比較大,冒泡、選擇、插入排序輔助空間開銷比較少。根據(jù)以上實(shí)驗(yàn)結(jié)果,可得出結(jié)論:當(dāng)記錄較小, 基本有序，要求穩(wěn)定時(shí)，則采用直接插入排序；若記錄較小，分布隨機(jī)，穩(wěn)定性不做要求時(shí)，則采用直接選擇排序；若記錄較大

12、，內(nèi)存允許，要求排序穩(wěn)定時(shí)，則采用歸并排序。所以在選擇合適的排序算法時(shí),應(yīng)該考慮到算法本身的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性等.其具體的用法應(yīng)根據(jù)應(yīng)用環(huán)境而定,側(cè)重點(diǎn)不同,則選擇的排序方法也各異。參考文獻(xiàn)1 王德超. 常用排序算法的分析與比較. 現(xiàn)代計(jì)算機(jī), 2012,6(1):36-40.2張銘,趙海燕,王騰蛟等.北京大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)設(shè)計(jì)J,計(jì)算機(jī)教育,2008,11(20):64-68.3葛建梅.數(shù)據(jù)結(jié)構(gòu)課程教學(xué)方法改革的思考J，中國成人教育,2008,9(1)，51-55.4范策,周世平,胡嘵琨等.數(shù)據(jù)結(jié)構(gòu)（C語言版）.機(jī)械工業(yè)出版社，2004，8（4）:81-93.5嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu).北京清華大學(xué)出版社,1997:263-289. 6曹衍龍,林瑞仲,徐慧.語言實(shí)例解析.北京人民郵電出版社,2007:94-117.7王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析.北京電子工業(yè)出版社,2007:21-25.8王穎,李肯立,李浪等.縱橫多路并行歸并算法.計(jì)算機(jī)研究與發(fā)展,2006,43(12):2180-2186.9周