算法渣-排序-希尔

没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法

定义

希尔排序是希尔(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

分组排序后,他们的索引还是保留在原始索引中,来两个更加直观的动画演示

image

image

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void shellSort(int []array) {
//以length/2为增量
for (int gap=array.length/2;gap>0;gap= gap/2) {
//以gap分组,进行排序
for(int i = gap;i<array.length;i++){
int tmp = array[i];
int j = i - gap;
//相对直接插入,步长从1变成了gap
while ( j>=0 && tmp<array[j] ) {
array[j+gap] = array[j];
j=j-gap;
}
array[j+gap] = tmp;
}
}
}

复杂度

希尔排序的时间复杂度与增量(即,步长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 1 No
公众号:码农戏码
欢迎关注微信公众号『码农戏码』