Excel VBA高级编程:希尔排序算法的原理

2015-04-13 14:02 阅读 225 次 评论关闭

希尔排序算法因科学家 Donald L. Shell 得名, 它是基于插入排序的, 但增加了一个特性,即增量排序,它在有间隔的元素中进行插入排序,然后减小间隔,直到为间隔1。 比如说先对下标为0,4.8的元素进行排序,然后对下标为 1,5,9的元素排序,接下来减小间隔, 如对 0,1 排序。
插入排序对基本有序的数组排序效率非常高,然而通常情况下, 如果有小的元素在最后, 则它几乎要移动 N 个位置才能来到前面, 平均也要 N/2 次,对于 N 个数来说, 移动的次数太多了。希尔排序使用增量,让元素可以大跨度地移动, 而不是一个一个地往前移, 那么经过很少次数的移动后, 数组会变成若干个小的基本有序的数组,到最后增量减为1的时候, 每个元素离自己的正确位置不过一两步而已。事实上在最后一步,增量减为1的时候,就是一个普通的插入排序了。刚开始对希尔排序可能不太理解, 但如果将插入排序看作是增量始终为1的希尔排序,则问题就迎刃而解。
增量的大小对效率的影响非常之大, 可能算法不仅是一种, 但通常认为, 增量序列应该是互质的, 且无论如何,最后都要保证增量的值为1。 Donald E. Knuth 的算法是 h = 3*h +1. 由于这些因素,它的时间复杂度通常在 O(N^2/3) ~ O(N^6/7) 之间。 按最坏的情况算, 接近于O(N^2/3).

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:Excel VBA高级编程:希尔排序算法的原理 | 猎微网

评论已关闭!