排序:(三)希尔排序

一、 特点

希尔排序(Shell Sort)是插入排序的一个扩展,它通过允许交换非相邻元素来提高执行效率。 该算法通过把原文件分解,然后使每第h个元素产生一个排好序的文件。 通过h到1的序列进行操作,最终产生一个排好序的文件。

实现每h个元素排序的一个方法是进行插入排序。 这时当最后一个步骤h=1时,这就是简单的插入排序了。

二、 序列的选择

序列的选择是个很难回答的问题,还没有证明最好的序列已经被找到。 在实际中常常使用以几何级别减少的序列。 得到一个好的步长序列的实际效果最多能大概提高25%的效率。 下面是三个已经证明较好的序列。

  1. 对步长序列为1 4 13 40 121 364 1093 3280 9841 ... 希尔排序使用少于O(N^(3/2))次的比较操作。(Knuth)
  2. 对步长序列为1 8 23 77 281 1073 4193 16577 ... 希尔排序使用少于O(N^(4/3))次的比较操作。( 4^(i+1)+3*2^i+1, i>0)
  3. 对步长序列为1 2 3 4 6 9 8 12 18 27 16 24 36 54 81 ... 希尔排序使用少于O(N(longN)^2)次的比较操作。(Pratt)

三、 总结

希尔排序具有较高的执行效率和代码简单容易执行的特点。 除非N很大,快速排序等较复杂的排序方法也只提供两倍的效率,而且要复杂的多。 因此希尔排序适合快速解决一个排序问题。

发表评论