希尔排序

希尔排序是一种高效排序算法和基于插入排序算法。该算法避免了大的变化作为插入排序的一种情况，如果较小的值很远右边那么必须移动到最左边。该算法采用插入排序上广为传播的元素先对它们进行排序，然后排序不太广泛分布的元素。 这个间距称为间隔。该间隔是根据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编程语言希尔排序的实现，请点击这里