王代星，袁琳琳

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

0 引 言

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

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

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

圖1 2-路插入排序示例

2 具有代表性的其他改進(jìn)算法

2.1 有分界元素的改進(jìn)算法

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

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

2.2 無分界元素的改進(jìn)算法

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

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

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

3 雙向交替折半插入排序

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

3.1 算法思想

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

具體做法如下：初始化左右兩端有序序列，比較r[0]與r[n-1]，若r[0]>r[n-1]，則交換r[0]與r[n-1]，保證左端的初始有序序列不大于右端的初始有序序列。設(shè)置兩個(gè)指針left與right，分別指向左端有序序列的最后一個(gè)元素和右端有序序列的第一個(gè)元素。初始時(shí)，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]移動(dòng)到left位置。此后，不斷重復(fù)左右交替掃描，直到left=right，算法結(jié)束。具體排序過程如圖2所示。

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

3.2 算法描述

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

輸入：隨機(jī)序列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]，算法結(jié)束。

3.3 算法分析

以下的分析，皆以隨機(jī)序列為例。

3.3.1 時(shí)間復(fù)雜度

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

3.3.2 空間復(fù)雜度

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

3.3.3 算法的穩(wěn)定性

由于插入排序是在序列的兩端交替進(jìn)行，同時(shí)為了保證右端的有序序列不小于左端的有序序列，元素會在兩端移動(dòng)，即序列左半部分的數(shù)據(jù)，有可能插入到右端的有序序列中，右半部分?jǐn)?shù)據(jù)也可能插入到左端有序序列中，因此，算法是不穩(wěn)定的。

4 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

通過實(shí)際測試，得出實(shí)驗(yàn)數(shù)據(jù)與結(jié)果，其中隨機(jī)序列的統(tǒng)計(jì)數(shù)據(jù)，是執(zhí)行了100次的平均數(shù)。另外，兩數(shù)據(jù)交換位置，按兩次數(shù)據(jù)移動(dòng)統(tǒng)計(jì)。

4.1 算法的數(shù)據(jù)比較和移動(dòng)次數(shù)

表1給出了算法在不同的排序規(guī)模和三種主要數(shù)據(jù)序列狀態(tài)下進(jìn)行排序時(shí)實(shí)際的數(shù)據(jù)比較次數(shù)。當(dāng)原序列為隨機(jī)時(shí)，比較次數(shù)不超過nlog2n-n/2次；正序時(shí)，為2n-3次；逆序時(shí)，為nlog2n/1.9次。

表1 雙向交替折半插入排序法的數(shù)據(jù)比較次數(shù)

表2給出了算法在不同的排序規(guī)模和三種主要數(shù)據(jù)序列狀態(tài)下進(jìn)行排序時(shí)實(shí)際的數(shù)據(jù)移動(dòng)次數(shù)。當(dāng)原序列為隨機(jī)時(shí)，移動(dòng)次數(shù)約為n2/8次；正序時(shí)，為0次；逆序時(shí)，為1.5n次。

表2 雙向交替折半插入排序法的數(shù)據(jù)移動(dòng)次數(shù)

4.2 幾種算法的比較

下面比較了直接插入、折半插入、2-路插入和雙向交替折半插入排序的實(shí)驗(yàn)數(shù)據(jù)。在圖表中，雙向交替折半插入排序簡稱雙向交替。實(shí)驗(yàn)數(shù)據(jù)分別按隨機(jī)、正序和逆序序列，給出數(shù)據(jù)比較次數(shù)和數(shù)據(jù)移動(dòng)次數(shù)的對比。

4.2.1 對隨機(jī)序列排序?qū)Ρ?/p>

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

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

表3 對隨機(jī)序列排序時(shí)的數(shù)據(jù)比較次數(shù)對比

表4 對隨機(jī)序列排序時(shí)的數(shù)據(jù)移動(dòng)次數(shù)對比

圖3 隨機(jī)序列數(shù)據(jù)移動(dòng)次數(shù)對比

4.2.2 對正序序列排序?qū)Ρ?/p>

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

表5 對正序序列排序時(shí)的數(shù)據(jù)比較次數(shù)對比

表6給出了4種算法的數(shù)據(jù)移動(dòng)次數(shù)的對比。2-路插入法需要移動(dòng)數(shù)據(jù)2n次；其他算法無需移動(dòng)數(shù)據(jù)。

表6 對正序序列排序時(shí)的數(shù)據(jù)移動(dòng)次數(shù)對比

續(xù)表6

4.2.3 對逆序序列排序?qū)Ρ?/p>

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

表7 對逆序序列排序時(shí)的數(shù)據(jù)比較次數(shù)對比

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

表8 對逆序序列排序時(shí)的數(shù)據(jù)移動(dòng)次數(shù)對比

4.3 結(jié) 論

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

5 結(jié)束語

總的來說，2-路插入排序及其改進(jìn)算法，其數(shù)據(jù)的移動(dòng)次數(shù)跟直接插入排序法還是一個(gè)數(shù)量級的，要徹底有所改進(jìn)，只有改順序存儲結(jié)構(gòu)為鏈?zhǔn)酱鎯Y(jié)構(gòu)，比如文獻(xiàn)[17]所述算法，但數(shù)據(jù)的比較次數(shù)又難以兼顧。實(shí)際應(yīng)用應(yīng)綜合考慮數(shù)據(jù)比較和移動(dòng)的代價(jià)。