希尔排序又称为缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
既然希尔排序是插入排序的改进版本，那么它们之间必定有相似之处。那么得先回忆下什么是插入排序？插入排序就是将一个数组分为两个区间：已排序区间和未排序区间。然后在未排序区间中取一个数，将其按照顺序插入到已排序区间，重复操作，保证已排序区间一直有序。
希尔排序是将整个有序序列分割成若干小的子序列分别进行插入排序，使数组中任意间隔为n的元素都是有序的，这个间隔n称为增量。
整个过程如下，首先设置一个增量大小，将原始序列中间隔为n的元素进行递增排序，使得这两个元素有序，接着对整个数组中所有元素都这样排序，当间隔为n的元素都有序之后，缩小增量，继续重复以上操作。
希尔排序用语言表述比较不直观，那就来看一张图，以数组{8,9,1,7,2,3,5,4,6,0}为例。
在增量=5时，首先进行排序的是(8,3)这一组数据，8>3，当(8,3)交换后，得到的序列为{3,9,1,7,2,8,5,4,6,0}。然后看看(8,3)这一组前面是否还有数据，发现没有了，于是进行下一组的排序。
下一组是(9,5)，因为9>5，所以9和5进行交换，交换后的序列为{3,5,1,7,2,8,9,4,6,0}，然后看看(9,5)这一组前面是否还有数据，发现还有一组我们上面排序后的(3,8)，它们的顺序是对的，因此继续下一组的排序。
下一组是(1,4)，因为1<4，所以1和4位置不变。然后看看(1,4)这一组前面是否还有数据，发现还有一组我们上面排序后的(3,8)和(5,9)，它们的顺序是对的，因此继续下一组的排序。
重复以上操作，完成增量为5的排序后，将增量减少，继续下一次的排序，直到整个数组有序为止。
那么增量应该改什么值合适？一般来说，每次增量都除以2。
package Sort;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
shellSort(arr);
System.out.println("arr = " + Arrays.toString(arr) );
}
public static void shellSort(int[] arr) {
// 增量初始化为数组长度的一半，每次都/2
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从增量位置那一组开始进行插入排序，直至完毕
for (int i = gap; i < arr.length; i++) {
int j = i; // 从i这个位置开始从后往前排序
int temp = arr[j]; // 先保存i位置的元素值，用于交换
// j - gap 就是代表与它同组的左边的元素
// j - gap >= 0：不越界
while (j - gap >= 0 && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j = j - gap; // 这一组比较过了继续往前比较，确定前面也有序
}
arr[j] = temp;
}
}
}
| 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|
| O(nlogn) | O(nlog2n) | O(n2 ) | O(1) | In-place | 不稳定 |
希尔排序的性能无法准确量化，跟输入的数据有很大关系，其时间复杂度介于O(nlogn) 到 O(n^2) 之间。对于大规模的序列（n>=1000），希尔排序都具有很高的效率。
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n2)好一些。
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。