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

希尔排序与之前的排序算法不同，她是以她的发明者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)。