希尔排序（Shell）

发表于 2022-03-15 分类于 Algorithm Changyan：

希尔排序

平均事件复杂度	最好情况	最坏情况	空间复杂度	稳定性	排序方式
$O(nlogn)$	$O(nlog^2 n)$	$O(nlog^2 n)$	$O(1)$	不稳定	In-place

简介

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。

提算法贡献者：D.L.Shell

提出时间：1959 年

算法思想

特点

基于插入排序

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

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

使用增量序列来排序（Gap sequences）

希尔排序的好坏与增量序列的选择有关。

希尔排序中比较著名的增量序列有：

v2-8080ea078aed21e0cfa427df93863138_r

排序动画

动图展示的是增量序列为：5，2，1

希尔排序

代码设计

确定增量序列

选取一个合适的增量序列，假设序列为gaps[]。（注意增量序列需要倒序处理，确保最后一个是1）

外层遍历增量序列

每次选取增量序列中的一个序列来进行排序

// foreach gaps[]
for(gap : gaps){
    // 内层进行跨增量的插入排序
}

内层进行跨增量的插入排序

首先从增量对应的数组下标开始，确定待排序数据范围

// 循环次数是数组长度减去当前增量值
for(int i = gap; i < array.length; i++){
    
}

然后在待排序数据范围循环内部，根据某个增量跨度，将增量跨度的元素进行排序

// 进行跨增量插排，比较当前下标的数据(array[j])和下标减掉增量的数据(array[j - gap])是否符合条件
// 如果最后j小于当前增量，则退出循环，i+1，继续进行插入排序
for(int j = gap; j >=gap && less(array[j], array[j - gap]); j -=gap)
    exch(array,j,j-gap);	// 交换两个变量

将所有代码拼起来就是：

public void shell(Comparable[] array, int[] gaps){
	// foreach gaps[]
	for(int gap : gaps){
    	// 内层进行跨增量的插入排序
    	for(int i = gap; i < array.length; i++){
    		for(int j = gap; j >=gap && less(array[j], array[j - gap]); j -=gap)
    			exch(array,j,j-gap);	// 交换两个变量
		}
	}
}

当然上面的代码是shell排序的通用模板，实际上写方法不唯一，如对于A003462增量序列，可以参考下面的代码：

// 序列：121,40,13,4,1 
int N = a.length;
int h = 1;
int inc = 3;
// 生成序列
while (h < N/inc)
    h = inc * h + 1;
	// 初始化增量跨度规模，从规模（下标）h开始，，最后一次相当于插入排序
while(h >= 1){
	// 内层是插入排序
    for (int i = h; i < N; i++){
        for(int j = i; j >= h && less(a[j], a[j-h]); j -= h)
            exch(a, j, j-h);
    }
    // 降低增量
    h /= inc;
}