希尔排序
又称缩小增量排序,只要最后一个增量是1,任何的序列都是可行的。在使用增量H之后,对于每一个i,我们有A[i]<=A[i+H],及所有相隔H的元素都被排序
- 最坏的运行时间是O(n^2)
- 最好的序列是{1,5,19,41,109…} 的项是[94^i-92^i+1]和[4^i-3*2^i+1]
简单实现(Java)
1 | public static void shellSort(int[]table){ |
- 使用Hibbard增量,平均运行时间是O(N^(5/4))
- 使用{1,5,19,41,109…}平均运行时间O(N(7/6))