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

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

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

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

示例代码

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,…),该序列的项来自9 4^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,…)

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

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章