经典算法巡礼(四) -- 排序之希尔排序

希尔排序与之前的排序算法不同,她是以她的发明者Donald Shell来命名的。她是插入排序的一种改进版本。

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

  • 插入排序的效率与输入序列有关,当输入序列处于基本排好序的情况下可以达到线性排序的效率;
  • 插入排序在大规模乱序情况下,效率是比较低的,因为她只会交换相邻的元素,因此元素只能一点点从数组的一端移动到另一端,即最差情况下的平方级别的效率。

希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。换句话说,希尔排序就是将数组中任意间隔为h的元素组成的新数组排列有序,当h为1时,该数组就排序完成了。事实上,h为1时,希尔排序就是插入排序

那么,为什么希尔排序会比较高效呢?首先,我们知道插入排序对于基本有序的数组排序效率是线性的。希尔排序在排序之初,间隔为h的元素组成的新数组都很短,而且基本处于有序状态,所以采用插入排序对子数组排序是很高效的。然后当h递减时,又由于已进行过几轮排序的原因,子数组又是基本牌有状态的,所以很适合采用插入排序

说了这么多,其实希尔排序就是将数组中元素以h为间隔取出元素组成新的数组,并用插入排序将新数组排列有序。递减h的值,重复以上过程,直到h==1为止。

那么,h应该如何递减呢?事实上要回答这个问题并不简单。希尔算法的性能不仅取决于h,还取决于各h之间的数学性质,比如它们的公因子等。这里,我们以h=h*3+1做为h的递增方法,用golang实现如下:

	// Sort方法从将间隔为h的元素组成的子数组进行插入排序,重复此过程直到h==1
	// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
	func (this *ShellSort) Sort(a []Comparable, compare Compare) {
		arrayLen := len(a)

		h := 1
		for h < arrayLen/3 {
			h = 3*h + 1
		}

		for h >= 1 {
			// 对间隔为h的子数组进行插入排序
			for i := h; i < len(a); i++ {
				for j := i; j >= h && this.less(a[j], a[j-h], compare); j -= h {
					this.exch(a, j, j-h)
				}
			}
			h = h / 3
		}
	}

这里,我们并不讨论希尔排序的时间复杂度,因为这个问题至今还没有确定的答案,但肯定的是,她是可以用于进行大规模数据的排序,在最坏情况下时间复杂度可以达到O(NlogN*logN)

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券