賈丹+張興

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

關鍵詞：時間復雜度；快速排序；歸并排序；完全二叉樹；深度

中圖分類號：TP311 文獻標識碼：A 文章編號：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

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

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

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

1.1 直接插入排序

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

1.2 快速排序

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

1.3 堆排序

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

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

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

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

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

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

對于快速排序，兩邊的兩個子序列長度不一定是相同的，如果兩個序列的長度相同或大致相同的話，速度會更快，效率會更高。

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

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

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

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

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

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

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

2.3 從n個記錄中選擇前k項（n值較大）

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

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

3 結束語

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

參考文獻：

[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）[M].北京：清華大學出版社，2008.

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

[3] 楊曉波.算法時間復雜性分析綜述[J].西藏大學學報：自然科學版 ，2011，26（1）： 87-90.

[4] 呂國英.算法設計與分析[M].北京：清華大學出版社，2009.

[5] 劉模群.排序算法時間復雜度研究[J].軟件導刊，2012，11（6）： 35-37.

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