希尔排序

引论

前面讲了插入排序,算法很简单,但是效率很糟糕。因为每次要将一个新的值插入到他的位置时,需要挪动很多的元素,这个效率就很差了,因此为了改进插入排序的效率,Donald Shell于1959年发明的一种改进插入排序的排序算法,也就是希尔排序。

对于插入排序我们知道,要想打破插入排序的时间界,那么必须要交换向距离比较远的元素。希尔排序通过引入增量序列,首先排序距离较远的元素,大大缩小逆序的数量,进而提高了插入排序的执行效率。

希尔排序

希尔排序利用一个增量序列,h1,h2,…,ht,任何增量序列只需要满足h1=1即可。在使用增量hk的排序中,只需要要满足A[i]<=A[i+hk]即可。也就是说使距离为hk的数据是有序的。希尔排序利用的原理就是首先交换距离较远的元素,减小逆序的数目。下面是一个小例子。

shellSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Shellsort(ElementType A[], int N)  
{
int i,j,Increment;
ElementType Tmp;
for(Increment=N/2;Increment>0;Increment /=2)
for(i=Increment;i<N;i++)
{
Tmp = A[i];
for(j=i;j>=Increment;j-=Increment)
{
if(Tmp<A[j-Increment])
A[j] = A[j-Increment];
else
break;
}
A[j] = Tmp;
}
}

这个代码只是对插入排序的代码进行了一点修改,就是加入了增量序列的循环,同时首先交换距离较远的元素。而不是每次交换临近元素。

关于希尔排序的一个比较主要的问题就是增量序列的选择问题。亦即是增量最大值ht,增量间距hk的选择问题。一个比较流行但是并不好的方法是:

$ h_t = \left \lfloor \frac{N}{2} \right \rfloor $

$ ht = \left \lfloor \frac{h{k+1}}{2} \right \rfloor $

希尔排序的增量序列的选择不同,算法的效率也会不一样。

Hibbard提出了一种增量序列1,3,7,…2^k-1.

shellSort1

总结

希尔排序通过引入增量序列,优先交换距离远的数据,减小逆序的个数,使排序时间缩短。

希尔排序简单,相对于插入排序高效,即使对于比较大的数据集也能取得比较不错的结果。

希尔排序通过减少逆序个数的方式,实际上减少的是在排序过程中重复的数据后移过程。

显示 Gitment 评论