一、基本原理
希尔排序听名字就能想到是Shell提出来的，只是对直接插入排序做了一个基本的改进。什么改进呢？
希尔排序是把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序
我们用一张图来表示一下：
上面的d表示间隔，也叫作增量，相同颜色的是一组。上面的元素看着花花绿绿的，不过找俩相同颜色的应该没什么大问题。
到了这有一个问题摆在大家面前了，也就是说一开始这个间隔应该取多少比较好呢？这里有一个公式：
上面10条数据，所以第一个增量是5。
还有一种计算的方式是这样的：增量的初始值是1，通过3*h+1循环计算，一直得到h刚好不大于数组长度。此时就取h做最大间隔。然后继需通过h=(h-1)/3来计算剩下的增量。
下面我们就使用代码来实现一下吧。
二、代码实现
我们来看一下简单的实现：
public static void shellSort(int[] array) { int number = array.length / 2; int i; int j; int temp; while (number >= 1) { for (i = number; i < array.length; i++) { temp = array[i]; j = i - number; while (j >= 0 && array[j] < temp) { array[j + number] = array[j]; j = j - number; } array[j + number] = temp; } number = number / 2; } }
上面就是希尔排序的基本实现算法，希尔排序本身就是对插入排序算法的一种改进，我们如何在这个基础上进一步作出改进呢？
这里有两个思路我觉得需要考虑：
（1）对增量序列优化：使用更加复杂的方式。
（2）对每一趟的插入排序进行优化：在内循环中，总是将较大的元素向右移动。
public static void ShellSort2(int arr[]) { int h = 1; int step = arr.length; //优化1 while (h < step / 3) { h = 3 * h + 1; } //优化2 int exchanges = 0; //交换次数 //若 arr[index] < arr[index - 1]，则交换两数 for (int index = step - 1; index > 0; index--) { if (arr[index]<arr[index - 1]) { exchange(arr[index],arr[index - 1]); exchanges++; } } //若交换次数为0（即数组有序），则无需进行下一步排序。 if (exchanges == 0) return; //若有交换次数，表明目前的数组无序。 while (h >= 1) { // 将数组变为 h 有序 for (int indexI = h; indexI < step; indexI++) { int temp = arr[indexI]; int indexJ = indexI; while (indexJ >= h && (temp<arr[indexJ - h])) { arr[indexJ] = arr[indexJ - h]; indexJ -= h; } arr[indexJ] = temp; } h = h / 3; }//while循环结束 }// 希尔排序结束
ok，这就是其优化，其实最主要的还是插入排序的优化，因为对于希尔排序而言，真正实现的还是插入排序。
三、分析
最佳情况：T(n) = O(nlogn)。 最坏情况：T(n) = O(n²)。 平均情况：T(n) = O(nlogn)。
希尔排序为什么这么有名气，是因为它是第一批突破o(n²)的排序算法之一。如有问题还请指正
