数据结构——希尔排序

杨伟彬
杨伟彬   编辑于 2018-12-28 13:59
阅读量: 66

1. 希尔排序原理

       希尔排序(Shell’s Sort)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破\(O(n^2)\)的第一批算法之一。

基本思想

       对待排序列先作“宏观”调整,再作“微观”调整。

排序过程

       先取一个\(d_1<n\)正整数,把所有相隔\(d_1\)的记录放在一组内,组内进行直接插入排序;然后取\(d_2 < d_1,\) 重复上述分组和排序操作;直至\(d_i= 1\),即所有记录放进一个组中排序为止。其中\(d_i\)称为增量

 

 

 

代码如下

void ShellInsert(SqList &L,int dk)
//对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比,做了以下修改
//1. 前后记录位置的增量是dk,而不是1;
//2. r[0]只是暂存单元,不是哨兵。当j <= 0时,插入位置已找到。
{
	int i, j;
	
	for(i = dk+1; i <= L.length; ++i)
	{
		if(LT(L.r[i].key, L.r[i-dk].key))	
		{//如果要插入的L.r[i]比L.r[i-dk].key小,插入前面
			L.r[0] = L.r[i];				//将L.r[i]暂存在L.r[0]
			for(j = i-dk; j > 0 && LT(L.r[0].key, L.r[j].key); 
j -= dk)
				L.r[j + dk] = L.r[j];		//记录后移,查找插入的位置
			L.r[j+dk] = L.r[0];				//插入L.r[0]
		}
	}
}

void ShellSort(SqList &L,int dlta[],int t)
	//按增量序列dlta[0...t-1]对顺序表L作希尔排序。
{
	int k;
	for(k = 0; k < t; ++k)
		ShellInsert(L, dlta[k]);	//一趟增量为dlta[k]的插入排序
}

算法分析

       (1)分组不是简单的“逐段分割”,而是将相隔某个增量的记录组成一个子序列。

       (2)增量序列取法

希尔最早提出的选法是\(d_1=⌊n∕2⌋,\)\(d_{i+1}=⌊(d_i )∕2⌋。\)

      克努特 (Knuth) 提出的选法是\(d_(i+1)=⌊(d_i-1)∕3⌋\)

     还有许多其他取法。如何选择增量序列以产生最好的排序效果,至今仍没有从数学上得到解决,一般遵循规则为:

              ①没有除1以外的公因子;

              ②最后一个增量值必须为1。

(3)希尔排序的时间复杂度约为:\(O(n^{1.3} )\)

 

收藏 转发 评论