雙向交替折半插入排序法

王代星，袁琳琳

(1.貴州大學 教育教學評估中心、高等教育研究所，貴州 貴陽 550025;2.貴州職業技術學院，貴州 貴陽 550023)

0 引 言

插入排序是計算機內部排序中最簡單的排序算法之一。它的基本思想是把第一個元素當作初始有序序列，從第二個元素開始，逐個將所有元素向前插入到該序列之中。插入排序主要有兩個基本操作，即查找插入位置時的數據比較和插入時的數據移動，通常把數據比較次數和數據移動次數作為算法的時間復雜度。根據查找插入位置方式的不同，又分為直接插入排序和折半插入排序。折半插入排序也可視為直接插入排序的改進算法，通過折半查找方式，減少了數據比較次數，但數據移動次數沒有改變。2-路插入排序[1]是折半插入排序的改進算法，能相對減少排序過程中數據的移動次數，但空間復雜度從O(1)增加到了O(n)，時間復雜度受第一個元素影響。當第一個元素是最大或最小的元素時，算法的時間復雜度變得與折半插入排序一致。針對這些不足，文中提出一種改進算法，即雙向交替折半插入排序算法。通過在待排序序列的兩端交替地插入排序，使數據移動次數比折半插入排序降低了50%、比2-路插入排序降低了25%，避免了2-路插入排序效率受分界元素影響的缺點，排序在序列的中間點結束，空間復雜度恢復為O(1)。

1 2-路插入排序算法簡介

對于長度為n的待排序序列r[0…n-1]，另設置等長的同類型數組d，將r[0]賦給d[0]，將數組d視為一個循環向量，排序在d中進行。將d[0]視作有序序列的中間元素，從r[1]開始，逐個將r中的元素插入到d中。具體插入方法是：對于待插元素r[i]，若r[i]

圖1 2-路插入排序示例

2 具有代表性的其他改進算法

2.1 有分界元素的改進算法

文獻[2]提出了一種名為“雙向插入排序法”的改進算法。其基本思想是：對于長度為n的待排序序列r[0…n-1]，排序在兩端進行。取r[0]、r[n/2]、r[n-1]三個元素中大小在中間的元素為分界元素，分別從右向左掃描和從左向右掃描待排序序列。在從右向左掃描時，將不小于分界元素的元素，向右側有序序列插入；當遇到小于分界元素的元素時，停止向左掃描，將該元素插入左側有序序列，然后開始從左向右掃描。在從左向右掃描時，將不大于分界元素的元素，向左側有序序列插入，當遇到大于分界元素的元素時，停止向右掃描，將該元素插入右側有序序列，然后又開始從右向左掃描。如此交替掃描和插入，直到處理完所有待排序元素為止。

雙向插入排序法優于2-路排序法，空間復雜度為O(1)，最終排序結果順序存儲在原序列中。但使用分界元素的不足之處仍未能避免。當分界元素碰巧為待排序序列的最大、最小，或次最大、次最小時，算法退化為單路插入，排序效率跟折半插入排序一致。與文獻[2]類似的還有文獻[3-5]提出的算法。

2.2 無分界元素的改進算法

文獻[6]提出了“循環插入排序法”。其算法的基本思想是：對于長度為n的待排序序列r[0…n-1]，把r[n/2]元素作為初始有序序列，即把有序序列安排在整個序列的中部，待排序元素兩側，插入在中部有序序列的兩端循環進行。設置兩個指針，分別指向中部有序序列的低端和高端。掃描待排序元素，當待排序元素大于有序序列中間的元素時，在有序序列的高端插入，高端指針向右移動加1；否則，在有序序列的低端插入，低端指針向左移動減1。直到所有持排序元素掃描結束為止。該算法的優點是每次數據移動的次數都不大于有序序列長度的一半，能夠有效減少數據的移動次數。但美中不足的是在排序過程指針越界時，要作循環處理；排序結束后，需要重新整理移動數據，需要1到n/2個數量不等的元素輔助空間。文獻[7-8]與文獻[6]的思路完全一樣，只是有序序列安排在循環序列的兩端。

文獻[9]提出了“一種新的2路插入排序算法”，排序在序列的兩端進行，待排序元素先與后端的最小元素比較，若大，則在后端插入；反之，則在前端插入。

其他的多路插入排序算法，有的增加了空間復雜度，有的增加了數據的比較次數，有的設置了一個或多個分界元素，比如文獻[10-16]等，此處不再詳述。

3 雙向交替折半插入排序

在沒有特別說明或不影響理解的情況下，算法即指雙向交替折半插入排序算法。

3.1 算法思想

以數據非遞減排序為例。對于給定長度為n的待排序序列r[0…n-1]，為不增加輔助空間，排序在原序列中進行，即原地排序；為有效減少數據移動次數，保證數據最終按非遞減排列，先在序列的左右兩端按非遞減排序，再逐漸向中間靠攏，同時保證右端有序序列的數據不小于左端有序序列的數據；為讓大的數據盡早向右移，讓小的數據盡早向左移，在掃描待排序數據時，采取從右向左和從左向右雙向交替掃描的方式，分別將大的數據插入右部有序序列和將小的數據插入左部有序序列，保證左右兩端的有序序列等長，排序最終在序列的中間點結束；在排序過程中，既要隨時保證右端有序序列數據不小于左端有序序列數據，同時也要充分利用這一特性，減少數據的比較和移動次數。在兩端有序序列中插入元素時，采用折半插入法，以減少數據的比較次數。

具體做法如下：初始化左右兩端有序序列，比較r[0]與r[n-1]，若r[0]>r[n-1]，則交換r[0]與r[n-1]，保證左端的初始有序序列不大于右端的初始有序序列。設置兩個指針left與right，分別指向左端有序序列的最后一個元素和右端有序序列的第一個元素。初始時，left=0，right=n-1。首先，從右端向左端掃描，比較r[right-1]與r[right]，若r[right-1]>r[right]，則r[right-1]向右端插入，指針right減1；若r[right-1]r[left+1]，則r[left+1]向左端插入，指針left加1；若r[left]r[right]，則r[left]向右端插入，r[right]移動到left位置。此后，不斷重復左右交替掃描，直到left=right，算法結束。具體排序過程如圖2所示。

圖2 雙向交替折半插入排序示例

3.2 算法描述

算法：雙向交替折半插入排序

輸入：隨機序列r[0…n-1]

輸出：非遞減序列r[0…n-1]

方法：

Step1:初始化。若r[0]>r[n-1]，則r[0]與r[n-1]交換；左端有序序列指針left=0；右端有序序列指針right=n-1；

Step2:從右端向左掃描。若r[right-1]>r[right]，則r[right-1]向右端插入，right--；若r[right-1]

Step3:從左端向右掃描。若r[left]>r[left+1]，則r[left+1]向左端插入，left++；若r[left]r[right]，則r[left]向右端插入，然后r[left]=r[right]。

Step4:若left

Step5:輸出r[0…n-1]，算法結束。

3.3 算法分析

以下的分析，皆以隨機序列為例。

3.3.1 時間復雜度

算法的排序時間主要消耗在數據的比較和移動上。由于計算機硬件環境和程序語言的差別，一般不用絕對運行時間來衡量排序算法的效率，而采用排序過程中所發生的數據比較次數和數據移動次數來衡量。算法的數據比較次數，主要發生在查找數據插入位置時。本算法在排序過程中，把有序序列均等地分布在序列的兩端，數據插入在兩端進行，減少了后半部分元素在插入有序序列時數據的比較次數，平均每個元素減少了1次，總的比較次數減少了約n/2次。傳統折半插入法平均數據比較次數為nlog2n，則本算法的平均數據比較次數不高于nlog2n-n/2。后文的實驗數據也證明了這一點。算法的數據移動次數，主要發生在數據插入時。同樣，由于數據插入是在兩端等長的有序序列中進行，每一端有序序列的長度，都相當于傳統的折半插入法排序時的有序序列長度的一半，故平均數據移動次數減半。傳統的折半插入法的平均數據移動次數約為n2/4，則本算法的平均數據移動次數約為n2/8。后文的實驗數據證明了，本算法的平均數據移動次數比傳統的折半插入法下降了50%，比2-路插入法下降了25%。

3.3.2 空間復雜度

從前面的算法分析和算法描述可以得知，本算法只需要一個元素輔助空間，作為數據交換時的臨時存儲空間，故空間復雜度為O(1)。

3.3.3 算法的穩定性

由于插入排序是在序列的兩端交替進行，同時為了保證右端的有序序列不小于左端的有序序列，元素會在兩端移動，即序列左半部分的數據，有可能插入到右端的有序序列中，右半部分數據也可能插入到左端有序序列中，因此，算法是不穩定的。

4 實驗數據與結果

通過實際測試，得出實驗數據與結果，其中隨機序列的統計數據，是執行了100次的平均數。另外，兩數據交換位置，按兩次數據移動統計。

4.1 算法的數據比較和移動次數

表1給出了算法在不同的排序規模和三種主要數據序列狀態下進行排序時實際的數據比較次數。當原序列為隨機時，比較次數不超過nlog2n-n/2次；正序時，為2n-3次；逆序時，為nlog2n/1.9次。

表1 雙向交替折半插入排序法的數據比較次數

表2給出了算法在不同的排序規模和三種主要數據序列狀態下進行排序時實際的數據移動次數。當原序列為隨機時，移動次數約為n2/8次；正序時，為0次；逆序時，為1.5n次。

表2 雙向交替折半插入排序法的數據移動次數

4.2 幾種算法的比較

下面比較了直接插入、折半插入、2-路插入和雙向交替折半插入排序的實驗數據。在圖表中，雙向交替折半插入排序簡稱雙向交替。實驗數據分別按隨機、正序和逆序序列，給出數據比較次數和數據移動次數的對比。

4.2.1 對隨機序列排序對比

表3給出了4種排序算法數據比較次數的對比。直接插入法的數據比較次數約為n2/4；折半插入、雙向交替和2-路插入不超過nlog2n。由于雙向交替法需要保證右端有序序列不小于左端有序序列，所以數據比較次數比2-路插入法要約高。通過表中數據計算，平均約高1.6%。

表4給出了4種算法數據移動次數的對比。直接插入和折半插入的數據移動次數是一樣的，約為n2/4；2-路插入約為n2/6；雙向交替約為n2/8。雙向交替比2-路插入約減少了25%。圖3顯示了數據移動次數隨著排序規模變化的趨勢圖，直接插入與折半插入重疊一致，雙向交替增長最緩慢。

表3 對隨機序列排序時的數據比較次數對比

表4 對隨機序列排序時的數據移動次數對比

圖3 隨機序列數據移動次數對比

4.2.2 對正序序列排序對比

表5給出了4種排序算法數據比較次數的對比。2-路插入法不僅是4種算法中數據比較次數最多的，而且通過與表3比較，數據比較次數還要約高于在隨機序列排序時，同樣約為nlog2n次；雙向插入為2n-3次；直接插入和折半插入為n-1次。

表5 對正序序列排序時的數據比較次數對比

表6給出了4種算法的數據移動次數的對比。2-路插入法需要移動數據2n次；其他算法無需移動數據。

表6 對正序序列排序時的數據移動次數對比

續表6

4.2.3 對逆序序列排序對比

表7給出了4種排序算法數據比較次數的對比。此時，直接插入的數據比較次數達到最高，約為(n-1)(n+2)/2次；2-路插入和折半插入相近，約為nlog2n次，跟隨機序列排序時的比較次數懸殊不大；雙向插入比較次數最少，約為nlog2n/1.9次，比2-路插入排序降低了47.37%。

表7 對逆序序列排序時的數據比較次數對比

表8給出了4種算法的數據移動次數的對比。此時，直接插入和折半插入的數據移動次數達到最高，為(n-1)(n+2)/2次；2-路插入為2n次；雙向交替約為1.5n次，比2-路插入排序降低了25%。

表8 對逆序序列排序時的數據移動次數對比

4.3 結 論

通過“3.3 算法分析”和“4 實驗數據與結果”得出，文章提出的雙向交替折半插入排序法，在對隨機序列進行排序時，數據比較次數不超過nlog2n-n/2次，數據移動次數約為n2/8次；在對正序序列進行排序時，比較次數為2n-3次，數據移動次數為0次；在對逆序序列進行排序時，比較次數約為nlog2n/1.9次，數據移動次數約為1.5n。與2-路插入法對比，在對隨機序列進行排序時，數據比較次數約增1.6%，數據移動次數約減25%；在對初始序列為正序或逆序序列排序時，也有比2-路插入法良好的表現；空間復雜度為O(1)，也比2-路插入法的O(n)少；且在排序時，當第一個元素為序列中最小或最大值的元素時，2-路插入法退化為單路插入，排序效率與折半插入排序一致，而雙向交替折半插入排序法則沒有這樣的缺點。綜上所述，雙向交替折半插入排序法的綜合性能優于2-路插入排序法。

5 結束語

總的來說，2-路插入排序及其改進算法，其數據的移動次數跟直接插入排序法還是一個數量級的，要徹底有所改進，只有改順序存儲結構為鏈式存儲結構，比如文獻[17]所述算法，但數據的比較次數又難以兼顧。實際應用應綜合考慮數據比較和移動的代價。