内部排序算法：希爾排序

基本思想

先取一個小于n的整數d1作為第一個增量，把待排序的全部記錄分成dx個組。所有距離為d1的倍數的記錄放在同一個組中。

先在各組内進行直接插人排序。

然後，取第二個增量d2<d1重複上述的分組和排序。

直至所取的增量dt=1(dt<dt-x<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

算法實作

希爾排序算法，java實作，代碼如下所示：

<code>public</code> <code>abstract</code> <code>class</code> <code>sorter {</code>

<code></code><code>public</code> <code>abstract</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array);</code>

<code>public</code> <code>class</code> <code>shellsorter</code><code>extends</code> <code>sorter {</code>

<code></code><code>@override</code>

<code></code><code>public</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array) {</code>

<code></code><code>int</code> <code>d = array.length;</code>

<code></code><code>shellpass(array, d);</code><code>// 根據逐漸減小的間隔增量，循環調用一趟排序</code>

<code></code><code>}</code><code>while</code> <code>(d ></code><code>1</code><code>);</code>

<code></code><code>* 希爾一趟排序</code>

<code></code><code>* @param d 間隔增量</code>

<code></code><code>private</code> <code>void</code> <code>shellpass(</code><code>int</code><code>[] array,</code><code>int</code> <code>d) {</code>

<code></code><code>integer tmp;</code>

<code></code><code>for</code> <code>(</code><code>int</code> <code>i = d; i < array.length; i++) {</code><code>// 數組下标從0開始，初始i=d表示一趟排序中第二個元素</code>

<code></code><code>tmp = array[i];</code><code>// array[i]的拷貝</code>

<code></code><code>// 如果待處理的無序區第一個元素array[i] < 有序區最大的元素array[i-d]</code>

<code></code><code>// 需要将有序區比array[i]大的元素向後移動</code>

<code></code><code>if</code> <code>(array[i] < array[i - d]) {</code>

<code></code><code>while</code> <code>(j >=</code><code>0</code> <code>&& tmp < array[j]) {</code>

<code></code><code>array[j + d] = array[j];</code><code>// 将左側有序區中元素比array[i]大的array[j+d]後移</code>

<code></code><code>// 如果array[i] >= 左側有序區最大的array[i-d]，或者經過掃描移動後，找到一個比array[i]小的元素</code>

<code></code><code>// 将右側無序區第一個元素tmp = array[i]放到正确的位置上</code>

<code></code><code>array[j + d] = tmp;</code>

希爾排序算法，python實作，代碼如下所示：

<code>class</code> <code>sorter:</code>

<code></code><code>abstract sorter class, which provides shared methods being used by</code>

<code></code><code>subclasses.</code>

<code></code><code>__metaclass__</code><code>=</code> <code>abcmeta</code>

<code></code><code>@abstractmethod</code>

<code></code><code>def</code> <code>sort(</code><code>self</code><code>, array):</code>

<code>class</code> <code>shellsorter(sorter):</code>

<code></code><code>shell sorter</code>

<code></code><code>length</code><code>=</code> <code>len</code><code>(array)</code>

<code></code><code>d</code><code>=</code> <code>length</code>

<code></code><code>while</code> <code>d></code><code>1</code><code>:</code>

<code></code><code># for each d, execute one pass shell sort</code>

<code></code><code>while</code> <code>i<length:</code>

<code></code><code>tmp</code><code>=</code> <code>array[i]</code>

<code></code><code>if</code> <code>array[i]<array[i</code><code>-</code><code>d]:</code>

<code></code><code>while</code> <code>j></code><code>=</code><code>0</code> <code>and</code> <code>tmp<array[j]:</code>

<code></code><code>array[j</code><code>+</code><code>d], array[j]</code><code>=</code> <code>array[j], array[j</code><code>+</code><code>d]</code>

<code></code><code>array[j</code><code>+</code><code>d]</code><code>=</code> <code>tmp</code>

排序過程

希爾排序的過程如下：

首先初始化間隔d為待排序數組的長度，無需排序。減小d，對于每次得到的間隔d，執行多組排序，使得原始數組間隔為d的一個子數組為有序，該數組通過類似直接插入排序的算法來執行排序。

直到，d減小為1的時候，整個數組為有序。這裡，采用二分的政策來得到間隔d。

下面通過例子來說明，執行希爾排序的過程，如下所示：

假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。整個排序過程的分組情況，如下所示：

下面說明詳細過程：

首先，初始化d = 20。在循環中反複得到間隔d，根據d執行一趟希爾排序。

對于d = 20/2 = 10：

根據d = 10來對數組排序，将原始數組分成2塊： {94,12,34,76,26,9,0,37,55,76}與{37,5,68,83,90,37,12,65,76,49}，也就是對如下數組分别進行直接插入排序：

{array[0],array[10]} = {94,37}

{array[1],array[11]} = {12,5}

{array[2],array[12]} = {34,68}

{array[3],array[13]} = {76,83}

{array[4],array[14]} = {26,90}

{array[5],array[15]} = {9,37}

{array[6],array[16]} = {0,12}

{array[7],array[17]} = {37,65}

{array[8],array[18]} = {55,76}

{array[9],array[19]} = {76,49}

第一趟希爾排序後，各個子數組變為：

{37,5,34,76,26,9,0,37,55,49}與{94,12,68,83,90,37,12,65,76,76}，

即：array = {37,5,34,76,26,9,0,37,55,49,94,12,68,83,90,37,12,65,76,76}，

對于d = 10/2 = 5：

根據d = 5來對數組排序，将第一趟希爾排序後的數組分成4塊：{37,5,34,76,26}、{9,0,37,55,49}、{94,12,68,83,90}與{37,12,65,76,76}，也就是對如下數組分别進行直接插入排序：

{array[0],array[5],array[10],array[15]} = {37,9,94,37}

{array[1],array[6],array[11],array[16]} = {5,0,12,12}

{array[2],array[7],array[12],array[17]} = {34,37,68,65}

{array[3],array[8],array[13],array[18]} = {76,55,83,76}

{array[4],array[9],array[14],array[19]} = {26,49,90,76}

第二趟希爾排序後，各個子數組變為：

{9,0,34,55,26}、{37,5,37,76,49}、{37,12,65,76,76}與{94,12,68,83,90}，

即：array = {9,0,34,55,26,37,5,37,76,49,37,12,65,76,76,94,12,68,83,90}。

對于d = 5/2 = 2：

根據d = 2來對數組排序，将第二趟希爾排序後的數組分成10塊： {9,0}、{34,55}、{26,37}、{5,37}、{76,49}、{37,12}、{65,76}、{76,94}、{12,68}與{83,90}，也就是對如下數組分别進行直接插入排序：

{array[0],array[2],array[4],array[6],array[8],array[10],array[12],array[14],array[16],array[18]} = {9,34,26,5,76,37,65,76,12,83}

{array[1],array[3],array[5],array[7],array[9],array[11],array[13],array[15],array[17],array[19]} = {0,55,37,37,49,12,76,94,68,90}

第三趟希爾排序後，各個子數組變為：{5,0}、{9,12}、{12,37}、{26,37}、{34,49}、{37,55}、{65,68}、{76,76}、{76,90}與{83,94}，

即：array = ：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}。

對于d = 2/2 = 1：

根據d = 1來對數組排序，将第二趟希爾排序後的數組分成20塊：{5}、{0}、{9}、{12}、{12}、{37}、{26}、{37}、{34}、{49}、{37}、{55}、{65}、{68}、{76}、{76}、{76}、{90}、{83}、{94}，也就是對如下數組分别進行直接插入排序：

{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}

第四趟希爾排序以後，數組已經有序：

array = {0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90,94}。

因為 d= 1，希爾排序結束。

算法分析

希爾排序是基于插入排序的一種算法，它的時間複雜度與增量序列的選取有關，例如：

希爾提出了增量序列 h1 ，h2 ，……，ht ，隻要h1=1，任何增量序列都是可行的，使用希爾增量排序的時間複雜度為o(n^2)。

hibbard提出了一個增量序列：2^k-1，使用hibbard增量排序的時間複雜度為o(n^(3/2))。

sedgewick提出了幾種增量序列：9*4i – 9*2i +1 或者是 4i – 3* 2i + 1，最壞運作時間為o(n^(4/3))，對這些增量序列的平均運作時間猜測為o(n^(7/6))。

但是現今仍然沒有人能找出希爾排序的精确下界。希爾排序沒有快速排序算法快o(nlogn)，是以中等大小規模表現良好，對規模非常大的資料排序不是最優選擇。但是比o(n^2)複雜度的算法快得多。

此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。專家們提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快，再改成快速排序這樣更進階的排序算法。

本質上講，希爾排序算法是直接插入排序算法的一種改進，減少了其複制的次數，速度要快很多，原因是，當n值很大時資料項每一趟排序需要的個數很少，但資料項的距離很長。當n值減小時每一趟需要和動的資料增多，此時已經接近于它們排序後的最終位置。正是這兩種情況的結合才使希爾排序效率比插入排序高很多。

時間複雜度

希爾排序的效率很大程度上依賴于增量序列的選擇，好的增量序列有如下共同特征：

最後一個增量必須為1。

應該盡量避免序列中的值（尤其是相鄰的值）互為倍數的情況。

有人通過大量的實驗，給出了較好的結果：當n較大時，比較和移動的次數約在n^1.25到1.6*n^1.25之間。

另外，希爾排序的時間性能優于直接插入排序，原因是：

當檔案初态基本有序時直接插入排序所需的比較和移動次數均較少。

當n值較小時，n和的差别也較小，即直接插入排序的最好時間複雜度o(n)和最壞時間複雜度0()差别不大。

在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組内直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使檔案較接近于有序狀态，是以新的一趟排序過程也較快。

是以，希爾排序在效率上較直接插入排序有較大的改進。

空間複雜度

因為希爾排序依賴于增量序列，進而導緻排序的趟數不固定，對于不同的增量執行一趟希爾排序，隻用到一個輔助變量，是以空間複雜度為o(n)。

排序穩定性

由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，通過上述元素76可以看到，希爾排序不穩定。

是以，希爾排序是不穩定的。

内部排序算法：希爾排序

繼續閱讀

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

shell排序基本思想及其複雜度分析

C++ 第十五周報告1--《冒泡法排序》

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希