內排序方法的選擇規則

王明芳

摘要:內部排序的方法很多,基于不同的運行環境,各種方法有各自的優點和缺點。就全面性能而言,無法指明哪種排序方法是最好的。為了提高計算機對數據處理的工作效率,本文對各種排序的方法和對應的算法進行了比較,進而選出最為適合的算法。

關鍵詞:內部排序;時間復雜度;空間復雜度

排序就是把一組記錄(元素)按照某個域的值的遞增或遞減的次序重新排列的過程。內部排序指的是待排序的記錄都存放在計算機內存中的排序過程。按排序的規則不同,可分為五類:插入排序、交換排序、選擇排序、歸并排序、基數排序。本文將對這五種排序方法進行比較,從而給出內排序的選擇規則。

1基本思想

1.1插入排序

插入排序的基本思想是:每次將一個待排序的記錄,按其關鍵字大小插入到前面已經排好序的子文件中的適當位置,直到全部記錄插入完成為止。插入排序方法有:直接插入排序和希爾排序。

1.2交換排序

交換排序的基本思想是:兩兩比較待排序記錄的關鍵字,發現兩個記錄的次序相反時即進行交換,直到沒有反序的記錄為止。應用交換排序基本思想的主要排序方法有:冒泡排序和快速排序。

1.3選擇排序

選擇排序的基本思想是:每一趟從待排序的記錄中選出關鍵字最小的記錄,順序放在已排好序的子文件的最后,直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。

1.4歸并排序

歸并排序是利用“歸并”技術來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件。這里,我們以兩路歸并方法做介紹。兩路歸并的基本思想是排序開始時將待排序列看成n個已排好序的子序列,每一個子序列中只含有一個記錄。將兩個相鄰的子序按算法merge逐一兩兩合并,得到n/2個有序子序列。每個子序列中含有2個記錄(最后一個可能只有1個記錄的子序列),這是第一趟歸并的結果。第二趟歸并在第一趟歸并的結果上進行,再將相鄰的子序逐一兩兩合并,得n/2/2個有序子序列。如此類推,直到最后歸并得到一個有序序列為止。

1.5基數排序

要了解基數排序,首先要了解桶式排序:如果我們有N個整數,范圍從1到M(或從0到M-1),我們留置一個數組A,大小為M,并初始化為0。于是該數組有M個單元(我們稱之為桶),開始他們都是空的。當數a被讀入時,A[a]增1。當所有的輸入被讀進時,掃描數組,打印出排好序的表。這就是所謂的桶式排序。

當M很大N很小時,空間嚴重浪費。這就推廣出基數排序。我們選取某個較小的數做為基數,比如10,那么我們就只需要10個桶。當M大于基數,我們采用多趟桶式排序。比如M=1000,那么我們需要3次桶式排序。具體做法是用最低有效位優先的方式,將各個數放入桶中;然后遍歷各個桶依據次最低有效位來調整,依次類推直到最高有效位。這便是基數排序的基本思想。

2比較

排序在計算機程序設計中非常重要,上面講述的各種排序方法各有其優缺點,適用的場合也不同。以下我們針對以上各種方法在時間復雜度、空間復雜度、穩定性及算法簡單性等幾方面進行比較。

2.1時間復雜度

從平均時間復雜度來考慮,直接插入排序、冒泡排序、直接選擇排序是三種簡單的排序方法,時間復雜度都為O(n2),而快速排序、堆排序、二路歸并排序的時間復雜度都為O(nlog2n),希爾排序的復雜度介于這兩者之間。

若從最好的時間復雜度考慮,則直接插入排序和冒泡排序的時間復雜度最好,為O(n),其它的最好情形同平均情形相同。

若從最壞的時間復雜度考慮,則快速排序的為O(n2),直接插入排序、冒泡排序、希爾排序同平均情形相同,但系數大約增加一倍,所以運行速度將降低一半,最壞情形對直接選擇排序、堆排序和歸并排序影響不大。

2.2空間復雜度

歸并排序的空間復雜度最大,為O(n),快速排序的空間復雜度為O(log2n),其它排序的空間復雜度為O(1)。

2.3穩定性

直接插入排序、冒泡排序、歸并排序是穩定的排序方法,而直接選擇排序、希爾排序、快速排序、堆排序是不穩定的排序方法。

2.4算法簡單性

直接插入排序、冒泡排序、直接選擇排序都是簡單的排序方法,算法簡單,易于理解,而希爾排序、快速排序、堆排序、歸并排序都是改進型的排序方法,算法比簡單排序要復雜得多,也難于理解。

3選擇規則

3.1根據時間/空間復雜度選擇

對元素個數較多的排序,可以選快速排序、堆排序、歸并排序,元素個數較少時,可以選簡單的排序方法。盡量選空間復雜度為O(1)的排序方法,其次選空間復雜度為O(log2n)的快速排序方法,最后才選空間復雜度為O(n)二路歸并排序的排序方法。

3.2一般性選擇規則

待排序元素的個數n較大,排序碼分布是隨機,而對穩定性不做要求時,則采用快速排序為宜。待排序元素的個數n大,內存空間允許,且要求排序穩定時,則采用二路歸并排序為宜。待排序元素的個數n大,排序碼分布可能會出現正序或逆序的情形,且對穩定性不做要求時,則采用堆排序或二路歸并排序為宜。待排序元素的個數n小,元素基本有序或分布較隨機,且要求穩定時,則采用直接插入排序為宜。待排序元素的個數n小,對穩定性不做要求時,則采用直接選擇排序為宜,若排序碼不接近逆序,也可以采用直接插入排序。冒泡排序一般很少采用?；鶖蹬判蚩稍贠(d × n)時間內完成對n個記錄的排序,d是指單邏輯關鍵字的個數,一般遠少于n。但基數排序只適用于字符串和整數這類有明顯結構特征的關鍵字。若n很大,d較小時,用基數排序較好。其它。前面討論的排序算法,除基數排序外,都是在向量存儲上實現的。當記錄本身的信息量很大時,為避免大量時間用在移動數據上,可以用鏈表作為存儲結構。插入排序和歸并排序都易在鏈表上實現,但有的排序方法,如快速排序和堆排序在鏈表上卻很難實現。

4結論

根據以上的論述及比較,我們看出,不同的運行環境,不同應用的需求,對算法的影響是很顯著的。有些算法理論上是優化了,但實際運行時就不一定最好的。我們無法確定一種算法是否是最優的:有的適用于n較大的情況;有的適用于n較小的情況;有的適用于初始序列基本有序;而有的又在初始序列基本有序時效率最低。因此不能一概而論,應該具體情況具體分析。

參考文獻

[1]嚴蔚敏,吳偉民數據結構(C語言版).北京:清華大學出版社 2000;

[2]Ellis Horowitz(美) 等. 譯者:李建中等數據結構(C語言版) .北京 機械工業出版社 2006

[3]徐孝凱.數據結構實用教程 .北京 清華大學出版社2006.