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