没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
定义
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一
算法
直接插入排序很循规蹈矩,不管数组分布是怎么样的,依然一步一步的对元素进行比较,移动,插入,比如[5,4,3,2,1,0]这种倒序序列,数组末端的0要回到首位置很是费劲,比较和移动元素均需n-1次
是否能够减少这样的移位呢?不希望是一步一步的移动,而是大步大步的移动。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
初始时,有一个大小为 10 的无序序列
在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组
接下来,按照直接插入排序的方法对每个组进行排序
在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组
按照直接插入排序的方法对每个组进行排序
在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组
按照直接插入排序的方法对每个组进行排序。此时,排序已经结束
演示
- 1.增量N/2=4分组
{35, 14}, {33, 19}, {42, 27} , {10, 44}
排序完:
- 2.增量N/2/2=2分组
{14, 27, 35, 42}, {19, 10, 33, 44}
排序完:
- 3.增量N/2/2/2=1分组排序
也可以通过动画更清晰了解整个排序过程
动画:http://www.zhuxingsheng.com/tools/sort/sort.html
分组排序后,他们的索引还是保留在原始索引中,来两个更加直观的动画演示
实现
1 | static void shellSort(int []array) { |
复杂度
希尔排序的时间复杂度与增量(即,步长gap)的选取有关
{1,2,4,8,…}这种序列并不是很好的增量序列,使用这个增量序列的时间复杂度(最坏情形)是O(n²)
Hibbard提出了另一个增量序列{1,3,7,…,2^k-1},这种序列的时间复杂度(最坏情形)为O(n^1.5)
Sedgewick提出了几种增量序列,其最坏情形运行时间为O(n^1.3),其中最好的一个序列是{1,5,19,41,109,…}
1 | 9×4^i−9×2i+1 和 4^i−3×2^i+1 这两个算式 |
其中, i=0,1,2,⋯ 时,第一个式子计算出的值分别为1,19,109,……; i=2,3,⋯ 时,第二个式子算出的值分别为5,41,……
Best | Average | Worst | Memory | Stable |
---|---|---|---|---|
n log(n) | depends on gap sequenc | n² | 1 | No |