希爾排序算法設計思想研究

謝　婷（1.馬鞍山市委黨校，安徽 馬鞍山243011；2馬鞍山電視大學，安徽 馬鞍山243011）

希爾排序算法設計思想研究

謝婷1，2
（1.馬鞍山市委黨校，安徽 馬鞍山243011；2馬鞍山電視大學，安徽 馬鞍山243011）

根據對希爾排序算法原理的研究分析，指出希爾算法的執行時間是受文件大小、掃描次數等因素影響，其中影響最大的是增量序列的選取，通過實驗證明，增量序列為N/3+1，N/9+1，N/27+1…，1時，程序排序效率比使用序列N/2，N/4，N/8，…，1要高。

希爾排序；算法；增量序列；時間復雜度

隨著計算機信息技術的普及，算法也已成為計算機學科的重要研究對象。算法這一詞匯是由數學家al-Khwarizmi的名字音譯過來的，直到1936年圖靈機這一現代計算機的基本模型出現后，算法的概念才算明確起來：算法就是按部就班地解決一個問題或完成一個目標的過程［1］。排序在算法中占有很重要的地位，排序算法在數據處理領域中是一種最常用的非數值算法，在計算機信息處理、數據庫操作、數據分析等方面起著重要的作用。希爾排序算法是Donald.L. Shell于1959年提出的一種插入排序算法。希爾算法所占用的內存少，排序速度快，這就使得這種排序算法在記錄較多時更具有使用價值。

一、希爾排序算法原理

希爾排序算法［2］：首先存在排列記錄R1，R2，…RN；在完成排序以后，它們的關鍵碼是有序的：K1＜= K2＜=…＜=KN。用一個輔助的增量序列ht，ht-1，…，h0來控制這個排序的過程，其中h0=1，t為程序的掃描次數｀；適當選擇增量可以顯著地減少排序時間，當t=1時，這個算法退化為直接插入排序法。

步驟1：［設置s循環］對s=t，t-1，…，0實施步驟2；然后結束這個算法。

步驟2：［設置j循環］設置h←hs，并對h＜j＜=N實施步驟3到步驟6（使用直接插入法來對隔開h個位置的記錄進行排序，使得1＜=i＜=N-h，Ki＜=Ki+h）。

步驟3：［設置i，K，R］置i←j-h，K←Kj，R←Rj。

步驟4：［比較K：Ki］若K＞=Ki，則轉到步驟6。

步驟5：［移動Ri，i減值］置Ri+h←Ri，然后i←ih。若i＞0，則轉回到步驟4。

步驟6：［R進入Ri+h］置Ri+h←R。

二、希爾排序算法實現

希爾排序也叫做“減少增量的排序”，因為每次掃描都是通過一個增量h來確定，使得我們對相距h個單位的記錄進行排序。希爾排序算法的實現如表1所示，最初有16個記錄進行排序，設其增量序列的取值為8，4，2，1。首先設置增量h=8，將這16個記錄分成8組，兩兩一組即（R1，R9），（R2，R10），…，（R8，R16）。分別對每組記錄進行排序，使得我們進到表的第3行，這一操作稱為“第一次掃描”。注意記錄R11150已經同記錄R3511交換了位置；記錄R5918和記錄R7886這兩條記錄都跳到右邊去了。現在減小增量設置h= 4，把得到的記錄重新分成4個組，每4個一組，即（R1，R5，R9，R13），…，（R4，R8，R12，R16），并再次分別對每組進行排序，這是“第二次掃描”，使得我們進入到表的第4行。第三次掃描再次減小增量設h=2，將得到的記錄分為2組，對各有8個記錄的兩個組進行排序，然后進行第四次掃描，通過對所有的16個記錄進行排序來完成整個過程。

希爾算法的代碼如下：

表1　增量為8，4，2，1的Shell排序

三、希爾算法的分析

希爾算法在初排序時，增量h取值較大，即間隔較大，子序列較多，每個序列中的記錄數目較少，所以子序列中用直接插入排序較快，隨著增量h減小即間隔變小，子序列中記錄數目增多，但由于已按上一個間隔排過序，記錄接近有序狀態，所以新的一趟排序過程也較快，在做最后一趟時，所有的排序碼幾乎有序了，大大提高了排序速度。

希爾算法的執行時間與5個因素有關：文件大小即排序的記錄數N，掃描次數即增量的個數t，增量序列ht，ht-1，…，h0，比較次數A，移動次數B。其中關鍵字的比較次數在這里又是重要因素，而關鍵字的比較次數又受著增量序列的影響，所以希爾算法研究的核心就是增量序列ht，ht-1，…，h0如何選取，才能使得希爾算法執行時間最短。

定理［2］：如果增量序列ht，ht-1，…，h0，滿足條件：hs+1modhs=0，對于t-1＞s＞=0，當排序記錄個數N很大時，希爾算法的運行時間不能比O（N1。5）更小。定理中整除性條件意味著，在每種（hs+1/hs）有序排列都是同等可能意義的。然而實踐證明，當N很大并且增量序列取值不滿足這個整除性條件時，算法的執行時間會更短，時間效率會更高。例如當增量序列選取…8，4，2，1時，在奇數和偶數位置上鍵值不相關時，希爾排序最后增量h為1時記錄移動次數O（N3/2），而當增量序列選取為…7，5，3，1時，最后增量h為1時記錄移動次數最多為2N次，排序時間得到明顯改善。所以我們有理由認為增量序列選取奇數序列比選取偶數序列要好，但并不一定是最好。理論上說，如果一個k有序的文件被h排序，則它保持為k有序。這一理論表明選取互素增量進行排序是可行的。

文中選取如下幾種方式進行驗證：⑴常用增量序列：N/2，N/4，N/8，…，1，易于簡單程序實現。⑵Hibbard序列［3］：2k-1，這樣得到的序列增量類似于奇數序列。 ⑶增量序列：N/3+1，N/9+1，N/27+1，…，1，這樣得到的序列不滿足整除條件。

四、實踐驗證

選取三組增量序列：

⑴ht1=N/2，N/4，N/8，…，1

⑵ht2=2k-1，…15，7，3，1

⑶ht3=N/3+1，N/9+1，N/27+1，…，1

代入希爾排序程序［4］，用隨機生成函數隨機產生三組大數量的無符號整數作為待排序記錄的關鍵字，分別用上述三種增量序列對各組待排序序列進行排序，記錄每個排序過程的比較次數、移動次數以及執行時間。

1.保持文件大小即排序的記錄數N不變

當N=100000，用隨機函數生成三組隨機數，分別代入上述三種增量序列對其進行希爾排序實驗。記錄實驗過程中的比較次數、移動次數和執行時間。測試結果記錄在表2：

表2　N值固定時三組隨機數據在不同增量序列下的測試結果

2.待排序列的記錄個數增加

記錄元素個數N的值從小到大變化（N=10000，100000，1000000，10000000）時，分別取三種增量序列代入同樣的希爾排序程序進行實驗，得到結果如表3：

表3　不同元素個數三種增量序列測試結果

根據表2表3的測試的結果來看，可以得出如下結論：

⑴對于記錄數相同的三組隨機生成的整數序列，在三種增量序列下排序中的比較次數、移動次數以及執行時間差別并不是很大。我們可以認為對于待排序序列的記錄數相同情況下，這三種增量序列，希爾排序算法的時間復雜度沒有明顯的差異。

⑵希爾算法受增量序列影響較大，選取恰當的h序列能縮短程序的執行時間。

⑶增量序列為N/3+1，N/9+1，N/27+1…，1時相對于其它兩種排序效率最優，隨著記錄個數的增多，優化效果越明顯。同時也印證了不滿足整除條件依然可以取得最優時間復雜度。特別要指出的是，ht3并不是唯一的最佳增量序列。

⑷奇數增量序列效率比偶數的要高。

［1］黃林鵬.基于歸納的算法設計思想［J］.程序員，2006（4）：56-58.

［2］DONALE E.Knuth計算機程序設計藝術（第3卷）排序與查找［M］.蘇運霖，譯.北京：國防工業出版社，2002：78-89.

［3］A.A.PAPERNOV G.V.Stasevich Problemy Peredachi Informatsii［M］.English translation in？Problems of Information Transmission Springer Publishing House.1965：81-98.

［4］劉瑞新.Visual C++面向對象程序設計教程［M］.北京：機械工業出版社，2004：79-88.

Research on the Design Idea of Shell Sorting Algorithm

Xie Ting1，2
（1.Ma＇anshan Mmunicipal Party Committee Party School，Ma＇anshan Anhui 243011，China；2.Ma＇anshan radio and Television University，Ma＇anshan Anhui 243011，China）

Based on the analysis of the research on the shell sort algorithm，the paper points out that Shell algorithm execution time is affected by the file size，number of scans and other factors，of which the influence is the largest increment series selection.Proved by experiments，the algorithm runs much better if it uses the sequence for N/3+1，N/9+1，N/27+1...，1 rather than the sequence of N/4，N/2，N/8，...，1.

Shell sort；algorithm；incremental sequence；time complexity

O223

A

1672-0547（2016）02-0111-02

2016-03-02

謝婷（1975-），女，安徽馬鞍山人，馬鞍山市委黨校（馬鞍山電視大學）講師，碩士，研究方向：計算機信息技術、網絡應用。