排序算法的性能分析

賈丹+張興

摘要：排序是計(jì)算機(jī)數(shù)據(jù)處理中的一種重要操作。在簡(jiǎn)單地討論直接插入排序、簡(jiǎn)單選擇排序、二路歸并排序、堆排序、快速排序等不同排序算法的思想及具體實(shí)現(xiàn)過(guò)程的基礎(chǔ)上，針對(duì)記錄數(shù)據(jù)分布無(wú)規(guī)律、記錄初始有序或基本有序、從n個(gè)記錄中選擇前k項(xiàng)（n值較大）等不同的數(shù)據(jù)分布形式，通過(guò)詳細(xì)的實(shí)驗(yàn)測(cè)試，對(duì)不同的排序算法做了細(xì)致的性能分析，從而實(shí)現(xiàn)在不同的數(shù)據(jù)分布下，提高排序算法的效率。

關(guān)鍵詞：時(shí)間復(fù)雜度；快速排序；歸并排序；完全二叉樹；深度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）26-0075-03

Performance Analysis of Sort Algorithm

JIA Dan， ZHANG Xing

（School of Electronic and Information Engineering， Liaoning University of Technology， Jinzhou 121001， China）

Abstract： Sort is a important operation in computer data processing.Based on disscussing briefly the idea and implementation process of different sort algorithm about straight insertion sort，quick sort，simple selection sort，heap sort and merging sort，a detailed performance analysis is finished according to experiment test for different cases including record data distribution without regular pattern， initial record order or basic order and select k items from n records（n is large） and so on.It is achieved that how to improve sort algorithm efficiency for different data distribution.

Key words：time complexity；quick sort；merging sort；complete binary tree；depth

排序是計(jì)算機(jī)程序設(shè)計(jì)中非常重要的操作之一，在系統(tǒng)的開(kāi)發(fā)過(guò)程中，經(jīng)常會(huì)涉及對(duì)數(shù)據(jù)的排序。所謂排序，就是將記錄按關(guān)鍵字的大小排列成一個(gè)非遞減或非遞增有序的序列。排序的方法有很多，常見(jiàn)的有插入排序、選擇排序、歸并排序、堆排序、快速排序、希爾排序等多種排序方法[1]。

在排序過(guò)程中，由于待排序數(shù)據(jù)的分布、表長(zhǎng)、數(shù)據(jù)的特征以及不同的排序方法實(shí)現(xiàn)的過(guò)程不盡相同，所以排序方法的效率也不相同。本文針對(duì)不同的待排序記錄序列，詳細(xì)地闡述了不同排序算法的效率，系統(tǒng)地分析了如何針對(duì)不同的初始待排序列選擇合適的排序算法，從而達(dá)到排序效率的最優(yōu)。

1 不同排序算法的思想及具體實(shí)現(xiàn)

1.1 直接插入排序

直接插入排序是一種簡(jiǎn)單的排序方法，其基本思想是依次將待排序記錄按照關(guān)鍵字的值插入到當(dāng)前的有序表中。初始有序表中只含第1個(gè)記錄，然后依次將第2、3…...n個(gè)記錄逐個(gè)插入，經(jīng)過(guò)n-1趟排序后，得到一個(gè)長(zhǎng)度為n的有序表。在排序過(guò)程中比較次數(shù)最大值和最小值分別為（n+4）（n-1）/2和n-1，所以直接插入排序的時(shí)間復(fù)雜度為O（n2） [2]。

1.2 快速排序

快速排序是一種先進(jìn)的排序方法，其基本思想是從待排記錄中選擇一個(gè)（通常第1個(gè)）記錄作為樞軸，以該記錄的關(guān)鍵字值為基準(zhǔn)，將待排記錄分成獨(dú)立的兩個(gè)子序列，其中一個(gè)子序列關(guān)鍵字的值均比樞軸記錄的大，另一個(gè)子序列關(guān)鍵字的值均比樞軸記錄的小。如初始序列為{90，63，21，33，45，95，120，10}，則經(jīng)過(guò)一趟快排后，序列變成{10，63，21，33，45}90{120，95}，前一個(gè)子序列關(guān)鍵字的值均比90小，后一個(gè)均比90大。完成一趟快排后，再分別選取前后兩個(gè)子序列中的第1個(gè)記錄作為樞軸，重復(fù)上述過(guò)程，直至所有記錄有序?yàn)橹埂?/p>

1.3 堆排序

堆排序也是一種先進(jìn)的排序方法，從排序方法上來(lái)說(shuō)，它是一種選擇排序的方法。堆排序是利用堆的特性進(jìn)行排序。堆排序的思想是首先根據(jù)排序要求建立一個(gè)堆，輸出堆頂（最小或最大）后，調(diào)整剩余元素成為一個(gè)新堆，這個(gè)過(guò)程稱之為篩選。之后，再輸出篩選后的新的堆頂（次小或次大），重復(fù)上述過(guò)程，直到輸出所有元素，此時(shí)按順序輸出的各堆頂?shù)闹稻褪且粋€(gè)有序序列。

除了上述的直接插入排序、快速排序、堆排序外，簡(jiǎn)單選擇排序、二路歸并排序都是常見(jiàn)的排序方法。不同排序算法的時(shí)間復(fù)雜度如表1所示。

2 不同數(shù)據(jù)分布時(shí)排序算法的性能分析

當(dāng)待排序記錄分布不同、數(shù)據(jù)特征不同時(shí)，排序算法的性能也不盡相同，不能一概而論。下面就待排記錄幾種不同的情況做詳細(xì)分析。

2.1 待排記錄數(shù)據(jù)分布無(wú)規(guī)律

如果待排記錄雜亂無(wú)章，也就是數(shù)據(jù)的分布沒(méi)有任何規(guī)律，從前面的分析，可以得出結(jié)論，快速排序所花費(fèi)的時(shí)間的常數(shù)因子k值最小[3]，所花費(fèi)的時(shí)間最短，此時(shí)快速排序的性能最優(yōu)，被認(rèn)為是效率最高的排序算法。下面圖1所示是8個(gè)待排記錄經(jīng)過(guò)三趟快排就完成了整個(gè)排序過(guò)程。

對(duì)于快速排序，兩邊的兩個(gè)子序列長(zhǎng)度不一定是相同的，如果兩個(gè)序列的長(zhǎng)度相同或大致相同的話，速度會(huì)更快，效率會(huì)更高。

2.2 待排記錄初始有序或基本有序

如果待排記錄有序時(shí)，快速排序反而失去了它的優(yōu)勢(shì)，蛻化為冒泡排序，如圖2所示。

從圖2可以看出，當(dāng)待排記錄初始有序時(shí)，快速排序每趟只是把樞軸記錄歸入到有序表，其他記錄仍在無(wú)序區(qū)中，已完全失去了快速排序的優(yōu)勢(shì)，時(shí)間復(fù)雜度也退化為O（n2） [4]，所以此時(shí)選擇快速排序是非常不可取的。

如果選擇堆排序、二路歸并排序等先進(jìn)的排序方法，它們的性能是不受待排數(shù)據(jù)影響的，均為O（nlog2n）。如果選擇簡(jiǎn)單選擇排序，在初始有序的情況下，雖然數(shù)據(jù)記錄移動(dòng)的次數(shù)為0，但對(duì)于數(shù)據(jù)比較次數(shù)，不受初始有序的影響，沒(méi)有發(fā)生任何改變，仍為n（n-1）/2，所以時(shí)間復(fù)雜度仍為O（n2） [5]。

對(duì)于初始有序的待排記錄，通過(guò)前面的分析，采用直接插入排序更快，在排序過(guò)程中，經(jīng)過(guò)n-1趟排序，每趟均是待插記錄和當(dāng)前有序表中最后一個(gè)記錄比，待插記錄總是大于當(dāng)前有序表中最后一個(gè)記錄，所以比較一次就結(jié)束，共n-1次比較，且不需記錄移動(dòng)，記錄次數(shù)為0。此時(shí)直接插入排序時(shí)間復(fù)雜度為O（n）級(jí)，待排記錄初始有序時(shí)不同排序算法的性能比較見(jiàn)表2所示。

從表2可以看出，當(dāng)初始有序時(shí)，直接插入排序需要比較的次數(shù)最少，性能最優(yōu)，效率最高。

通過(guò)上面的分析發(fā)現(xiàn)一個(gè)問(wèn)題：如何判定待排數(shù)據(jù)的分布特征，從而選擇相應(yīng)的高效的排序算法。數(shù)據(jù)分布的特征，我們也可以通過(guò)所有相鄰數(shù)據(jù)的比較來(lái)實(shí)現(xiàn)，如果前者比后者小的記錄數(shù)目占的比重較大，其有序高較高；反之則有序程度低，數(shù)據(jù)分布沒(méi)有規(guī)律，通過(guò)數(shù)據(jù)的有序度來(lái)選擇相應(yīng)的排序算法提高效率。

2.3 從n個(gè)記錄中選擇前k項(xiàng)（n值較大）

如果待排記錄的n值很大，特別是只要前若干個(gè)數(shù)據(jù)時(shí)，堆排序比較適合。例如要得到1000個(gè)數(shù)據(jù)記錄中的前8個(gè)，在上述的排序方法中，堆排序的效率是最高的。對(duì)于快速排序、二路歸并排序和直接插入排序，它們必須在得到整個(gè)有序序列后才能得到前8位，也就是說(shuō)，需要先把1000個(gè)數(shù)據(jù)進(jìn)行完整的排序，得到它們的有序序列后再?gòu)闹腥〕銮?位，可想而知，所花費(fèi)的時(shí)間是相當(dāng)長(zhǎng)的。

簡(jiǎn)單簡(jiǎn)單選擇排序和堆排序不必如此，它們?cè)诮?jīng)過(guò)若干趟排序后可以得到部分有序子序列。對(duì)于簡(jiǎn)單選擇排序，第一趟從n個(gè)元素中選擇最小的需要n-1次比較；第二趟從n-1個(gè)元素中選擇最小的需要n-2次比較…...，如果選擇出前8名，則需八趟排序，共需的比較次數(shù)為（n-1）+（n-2）+…...（n-8）=8n-36次。在堆排序中，對(duì)于深度為k的堆，初始建堆需要4n次比較[6]，以后每次從堆中篩選中一個(gè)最小值需比較2（k-1）次。由完全二叉樹的性質(zhì)，得到k=└log2n┘+1，n值依次從n-1開(kāi)始遞減1，由于遞減1對(duì)n值影響不大，可以均用n來(lái)表示堆中元素個(gè)數(shù)。則得到前8名需要建堆一次，篩選七次，比較次數(shù)小于4n+2（k-1）*7，k=└log2n┘+1=└log21000┘+1=10，經(jīng)過(guò)推導(dǎo)，可以得出比較次數(shù)小于4n+126，與簡(jiǎn)單選擇排序的8n-28次比較相比，少了大約4000次。表3列出了不同的排序方法從n個(gè)記錄中選擇前k項(xiàng)（例如k=8）時(shí)所需進(jìn)行的比較次數(shù)，經(jīng)過(guò)數(shù)據(jù)分析，可以得出，堆排序初始建堆時(shí)需要較多的比較次數(shù)，但在以后的每次篩選過(guò)程中，比較次數(shù)會(huì)發(fā)生質(zhì)的減少，大大提高排序速度，所以，堆排序?qū)τ诖庞涗浀膎值很大的情形，效率非常高。

3 結(jié)束語(yǔ)

排序是計(jì)算機(jī)系統(tǒng)開(kāi)發(fā)過(guò)程中，非常普遍又非常重要的操作之一，是將一組記錄的任意序列按關(guān)鍵字大小重新排列成為一個(gè)有序序列。本文詳細(xì)地討論了直接插入排序、簡(jiǎn)單選擇排序、二路歸并排序、堆排序、快速排序等幾種常見(jiàn)的排序方法的思想、排序過(guò)程及算法實(shí)現(xiàn)，系統(tǒng)地分析了當(dāng)數(shù)據(jù)分布沒(méi)有規(guī)律、記錄初始有序或基本有序、記錄數(shù)目多等幾種情況下，不同的排序算法的性能。最終實(shí)現(xiàn)在不同的數(shù)據(jù)分布下，如何選擇高效率的算法，使得排序效率最高，最節(jié)省時(shí)間。

參考文獻(xiàn)：

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

[2] 于曉敏，袁琪.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：北京航空航天大學(xué)出版社，2010.

[3] 楊曉波.算法時(shí)間復(fù)雜性分析綜述[J].西藏大學(xué)學(xué)報(bào)：自然科學(xué)版 ，2011，26（1）： 87-90.

[4] 呂國(guó)英.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2009.

[5] 劉模群.排序算法時(shí)間復(fù)雜度研究[J].軟件導(dǎo)刊，2012，11（6）： 35-37.

[6] 梁利剛，易超，楊繡丞， 郝樹偉.靜態(tài)排序算法設(shè)計(jì)與分析[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（3）： 283-286.