希爾排序

希爾排序是一種高效排序演算法和基於插入排序演算法。該演算法避免了大的變化作為插入排序的一種情況，如果較小的值很遠右邊那麼必須移動到最左邊。該演算法採用插入排序上廣為傳播的元素先對它們進行排序，然後排序不太廣泛分佈的元素。 這個間距稱為間隔。該間隔是根據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編程語言希爾排序的實現，請點擊這裏