经典排序算法 - 希尔排序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,…)

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