逍遥游

经典排序算法 - 希尔排序Shell Sort

简单介绍

希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布。

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本,本质上是一种分组插入排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

1、插入排序在对几乎已经排好序的数据操作时,效率高,可以达到线性排序的效率

2、但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

算法原理

将序列分组为较小的子序列,然后再利用直接插入排序进行组内排序,继而逐步增大组的大小,直到与原序列相同大小。

注意:不要与归并排序相混淆,看到网上有网友把归并排序与希尔排序的细节搞错了。尽管归并排序看起来也是从小到大合并,但是本质上是不一样的:归并排序的分是将相邻的元素化为一组,而希尔排序则是按照步长来分组的。打个比方,军训的时候,教官从第一个人数到第八个人然后说“你们一组”,这是归并排序;而希尔排序则是,教官说“从一个人开始,依次报数,奇数的是一组”。我想,大家应该能明白了吧。

希尔排序演示 希尔排序演示(来自维基)

具体实例演示

下面用希尔排序来对数组 {13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10} 排序(按照2i的分组序列)

Step 1

首先,我打算分为两个一组,共有16个数,就是八组,步长为8。

{13,65} {14,23} {94,45} {33,27} {82,73} {25,25} {59,39} {94,10}

组内用直接插入排序,得到

{13,65} {14,23} {45,94} {27,33} {73,82} {25,25} {39,59} {10,94}

Step 2

第二步,将新序列分为四个一组,共有四组,步长为4

{13,45,73,39} {65,94,82,59} {14,27,25,10} {23,33,25,94}

组内用直接插入排序,得到

{13,39,45,73} {59,65,82,94} {10,14,25,27} {23,25,33,94}

Step 3

第三步,八个一组,共两组,步长为2

{13,45,59,82,10,25,23,33} {39,73,65,94,14,27,25,94}

组内用直接插入排序,得到

{10,13,23,25,33,45,59,82} {14,25,27,39,65,73,94,94}

Step 4

第四步,16个一组,共一组,得到

{10,13,23,25,33,45,59,82,14,25,27,39,65,73,94,94}

组内用直接插入排序,得到

{10,13,14,23,25,25,27,33,39,45,59,65,73,82,94,94}

排序完成。

太原理工大学也有动态的演示,可以看看。网址:http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/shell_sort.asp

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void shellSort2(int *src, int size)
{
int step = size / 2;
int j,tmp;
while(step >= 1)
{
for(int i=0; i<size; i+=step)
{
//从第一个元素开始,每次取出一个加入到有序序列中
j = i;
tmp = src[i];
while(j>0 && tmp<src[j-step]){
//找到新元素在有序序列中的位置
src[j] = src[j-step];
j-=step;
}
src[j]=tmp;
}
step/=2;
}
}

详细代码请点击这里查看。

算法复杂度及稳定性

首先说稳定性。由于希尔排序分组是具有跳跃性的,故不稳定。

(以下主要参考自维基百科)

复杂度方面,shell算法的性能与所选取的分区长度序列有很大关系。前面的实例是最简单的分组长度序列,及n/2i ,最坏情况下时间复杂度是O(n^2)。

已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…),该序列的项来自94^i - 9 2^i + 1和2^{i+2} * (2^{i+2} - 3) + 1这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作,而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快,甚至在小数组中比快速排序还快,但是在涉及大量数据时希尔排序还是比快速排序慢。

尽管看起来,用了好多次直接插入排序,但是每次都是对基本有序(或者数量少)的序列进行排序,充分发挥了直接插入排序的优势,故希尔排序一般是优于直接插入排序的。

另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列):(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)

对了,突然想到上次说自底向上的归并排序跟希尔排序很像,这次得出结论了,正如我在上文中提到的,它们在细节上是有差别的。


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com