常用排序算法的研究

陳舜青

摘要：現(xiàn)實(shí)生活中常常需要從大量信息中查找需要的信息。為使查找更加有效和便捷，需要按特定次序?qū)π畔㈩A(yù)先排序后存儲(chǔ)，如按字母排列、分門(mén)別類存放圖書(shū)文獻(xiàn)。排序廣泛應(yīng)用于數(shù)據(jù)處理、情報(bào)檢索、商業(yè)金融等領(lǐng)域。排序是程序設(shè)計(jì)中處理數(shù)據(jù)最基本的算法之一。本文就常用排序方法討論其基本思想、實(shí)現(xiàn)過(guò)程，對(duì)排序的穩(wěn)定性以及時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行了分析。

關(guān)鍵詞：排序算法；提高效率；復(fù)雜度

一、幾種排序算法的比較

插入排序：每次把一個(gè)待排序的記錄插入到已排序的序列中，直到所有的記錄都插入為止。主要有直接插入排序和希爾排序，希爾排序的執(zhí)行時(shí)間取決于增量序列。

交換排序：兩兩比較待排序的關(guān)鍵字，如果次序是反序的就交換，直到?jīng)]有反序的記錄為止。主要有冒泡排序和快速排序。

選擇排序：每一次從待排序的記錄中找出一個(gè)最小值放最前面，直到所有的記錄都排好。

通過(guò)實(shí)例操作驗(yàn)證，在大數(shù)據(jù)下，排序時(shí)間從多到少的次序依次為：冒泡排序、選擇排序、插入排序、希爾排序、堆排序、快速排序。

二、排序的穩(wěn)定性分析

如果排序前兩個(gè)相同的數(shù)字間的位置關(guān)系與排序后的位置相同，那么這種排序算法是穩(wěn)定的，反之是不穩(wěn)定的。冒泡排序和直接插入排序?qū)儆诜€(wěn)定排序；直接選擇排序、快速排序和希爾排序?qū)儆诓环€(wěn)定排序。

若排序碼是關(guān)鍵碼，則對(duì)任意待排序序列經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼不是主關(guān)鍵碼，可能具有相同關(guān)鍵碼的多個(gè)記錄。

排序一般希望算法比較簡(jiǎn)單，占用輔助空間較小，運(yùn)行時(shí)間短。每一種算法都有自己的優(yōu)缺點(diǎn)，適合在某些特定的環(huán)境下使用。

三、時(shí)間復(fù)雜度和空間復(fù)雜度

評(píng)價(jià)一種排序方法的好壞，主要通過(guò)時(shí)間代價(jià)和空間代價(jià)衡量。排序過(guò)程中基本操作是關(guān)鍵碼和記錄的移動(dòng)，所以時(shí)間代價(jià)是以關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)衡量的，記錄的數(shù)量和大小、排序表的大小、原始序列的排序狀態(tài)都會(huì)影響排序時(shí)間。

直接插入排序，空間復(fù)雜度為O（1），時(shí)間復(fù)雜度為O（n2）；折半插入排序空間復(fù)雜度為O（1），定位一個(gè)關(guān)鍵碼的位置需要比較次數(shù)至多為log2（n+1）次，時(shí)間復(fù)雜度為O（nlog2n）。折半插入排序只能減少關(guān)鍵字間的比較次數(shù)，而移動(dòng)記錄的次數(shù)和直接插入排序相同，故時(shí)間復(fù)雜度仍為O（n2）。這也是一種穩(wěn)定排序方法，只適合順序存儲(chǔ)的排序表。交換排序的基本思想：通過(guò)排序表中兩個(gè)記錄關(guān)鍵碼的比較，若與排序要求相逆，則將兩者交換，直到?jīng)]有反序的記錄為止。

盡管快速排序的最壞時(shí)間為O（n2），但就平均性能而言，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快的，也因此稱為快速排序，它的平均時(shí)間復(fù)雜度為O（nlgn）。

四、排序方法的選擇

從算法實(shí)現(xiàn)來(lái)看，各種排序算法各有優(yōu)缺點(diǎn)，沒(méi)有絕對(duì)最優(yōu)的。使用時(shí)要根據(jù)不同情況選用，還可以將多種方法結(jié)合使用。需要考慮的因素有：待排序的記錄個(gè)數(shù)、每個(gè)記錄的大小、關(guān)鍵字的結(jié)構(gòu)和初始狀態(tài)、對(duì)排序穩(wěn)定性的要求、存儲(chǔ)結(jié)構(gòu)。

待排序記錄個(gè)數(shù)n較小時(shí)，n2和nlog2n區(qū)別不大，可選用簡(jiǎn)單的排序方法。排序方法的選擇主要根據(jù)以下情況來(lái)考慮：

第一，最適用于n值很大而關(guān)鍵字較小的序列，使用條件比較嚴(yán)格，需要知道各級(jí)關(guān)鍵字的取值范圍，只適合整數(shù)和字符這類有明顯特征的關(guān)鍵字。

第二，當(dāng)排序按記錄的主關(guān)鍵字進(jìn)行時(shí)，排序方法是否穩(wěn)定無(wú)關(guān)緊要；若排序按記錄的次關(guān)鍵字進(jìn)行，則必須采用穩(wěn)定的排序方法。

第三，大多數(shù)排序方法采用順序表來(lái)實(shí)現(xiàn)，若記錄本身信息量較大，為避免移動(dòng)記錄耗費(fèi)大量時(shí)間，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

對(duì)常規(guī)排序方法適當(dāng)改進(jìn)可以提高效率，比如：雞尾酒排序，是對(duì)冒泡排序的改進(jìn)，效率有所提高，也叫定向冒泡排序。此算法與冒泡排序的不同處是先從低到高，再?gòu)母叩降?，最差時(shí)間復(fù)雜度O（n2），最優(yōu)時(shí)間復(fù)雜度O（n），平均時(shí)間復(fù)雜度O（n2），所需輔助空間O（1），屬于穩(wěn)定排序。而冒泡排序僅從低到高逐個(gè)比較序列中的元素。

五、結(jié)語(yǔ)

排序主要是用來(lái)檢索、選擇、評(píng)估數(shù)據(jù)，把無(wú)序的數(shù)據(jù)或記錄序列重新組織成按關(guān)鍵字排列的有序序列。影響排序速度的因素有多種，待排元素的應(yīng)用領(lǐng)域、初始狀態(tài)、數(shù)據(jù)的多少和大小等。根據(jù)不同情況靈活選擇排序算法，才能提高排序速度、程序執(zhí)行效率。隨著對(duì)排序算法研究的深入，一定會(huì)有更多的優(yōu)秀算法及理論被應(yīng)用于實(shí)際工作中。

參考文獻(xiàn)：

[1]張小莉，等.數(shù)據(jù)結(jié)構(gòu)與算法（第3版）[M].北京：機(jī)械工業(yè)出版社，2014.

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

[3]連順金.快速排序的一種改進(jìn)算法[J].三明學(xué)院學(xué)報(bào)，2009，26（4）.

[4]陳琳琳，等.數(shù)據(jù)結(jié)構(gòu)與算法（C語(yǔ)言版）（第3版）[M].北京：清華大學(xué)出版社，2015.