希爾排序

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