希爾排序

希爾排序是一種高效排序算法和基於插入排序算法。該算法避免了大的變化作爲插入排序的一種情況，如果較小的值很遠右邊那麼必須移動到最左邊。該算法採用插入排序上廣爲傳播的元素先對它們進行排序，然後排序不太廣泛分佈的元素。 這個間距稱爲間隔。該間隔是根據Knuth的公式所計算 (h=h*3 +1) 其中h爲間隔並且初始值是1。該算法是用於中等大小的數據組很有效，因爲它的平均和最壞情況的複雜性是O(n)，其中n爲項目數量。

僞代碼

procedure shellSort( A : array of items )
int innerPosition, outerPosition
int valueToInsert, interval = 1

/* calculate interval*/
while interval < A.length /3 do:
interval = interval * 3 +1

while interval > 0 do:
for outer = interval; outer < A.length; outer ++ do:
/* select value to be inserted */
valueToInsert = A[outer]
inner = outer;

     /\*shift element towards right\*/
     while inner > interval -1 && A\[inner - interval\] >= valueToInsert do:
        A\[inner\] = A\[inner-1\]
        inner = inner - interval
     end while

     /\* insert the number at hole position \*/
     A\[inner\] = valueToInsert

  end for

  /\* calculate interval\*/
  interval = (interval -1) /3;      

end while

end procedure

要查看C編程語言希爾排序的實現，請點擊這裏