希尔排序是在插入排序的基础上进行优化，主要是减少插入次数。 例子中使用的待排序数据 {3, 32, 1, 55, 0, 3, 9}
排序规则是从左到右，从小到大排序，正确排序的结果：{0, 1, 3, 3, 9, 32, 55}
一、希尔排序源码
public class ShellSort {
public void shellSort(int array[]) {
if (array == null) {
throw new NullPointerException();
}
// 1 选择步长
for (int gap = array.length / 2; gap > 0; gap/=2) {
// 2 对所有组进行遍历
for (int i = 0; i < gap; i++) {
// 3 遍历组内所有元素
for (int j = i + gap; j < array.length; j += gap) {
// 4 组内元素比较大小
if (array[j - gap] > array[j]) {
// 5 插入排序
int insertValue = array[j];
int k = j - gap;
while (k >= 0 && array[k] > insertValue) {
array[k + gap] = array[k];
k -= gap;
}
array[k + gap] = insertValue;
}
}
}
}
}
public static void main(String[] args) {
int[] array = {3, 32, 1, 55, 0, 3, 9};
ShellSort shellSort = new ShellSort();
shellSort.shellSort(array);
System. out.println( Arrays.toString( array ) );
}
}
二、希尔排序逐步解释
1. 选择步长for (int gap = array.length / 2; gap > 0; gap/=2) {}
什么是步长？ 相隔几个元素进行比较，如果步长的规则是 gap = array.length / 2, gap /= 2; 每次都除以2，例子的步长选择就是： 数组长度 length = 7，所有步长分别是 3, 1 gap = 7/2 = 3 gap = 3/2 = 1
如何选择最优步长？ 这里使用的每次都是除以2，关于希尔排序最优步长的研究可以查看百科《希尔排序 - 维基百科 》 、 《希尔排序 - 百度百科》。
2. 对所有组进行遍历
for (int i = 0; i < gap; i++) {}
当前操作是嵌套在1中，即步长为3的时候执行一次，步长为1的时候执行一次。1中计算出步长（gap）的值分别是3, 1。
| gap取值 | i取值 |
| 3 | 0,1,2 |
| 1 | 1 |
3. 遍历组内所有元素
for (int j = i + gap; j < array.length; j += gap) {}
| gap取值 | i取值 | j取值 |
| 3 | 0 | 3,6 |
| 3 | 1 | 4 |
| 3 | 2 | 5 |
| 1 | 1 | 1,2,3,4,5,6 |
4. 组内元素比较大小
if (array[j - gap] > array[j]) {}
数组索引与值的对应关系
| 数组索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 对应值 | 3 | 32 | 1 | 55 | 0 | 3 | 9 |
4.1 步长为3时
| gap取值 | i取值 | j取值 | 比较 | 判断 |
| 3 | 0 | 3 | a[0] > a[3] | 3 > 55 |
| 3 | 0 | 6 | a[3] > a[6] | 55 > 9 |
| 3 | 1 | 4 | a[1] > a[4] | 32 > 0 |
| 3 | 2 | 5 | a[2] > a[5] | 1 > 3 |
{3, 32, 1, 55, 0, 3, 9}上面的表格也可以写成，步长为3： 3与55比较 55与9比较 32与0比较 1与3比较
4.2 步长为1时
| gap取值 | i取值 | j取值 | 比较 | 判断 |
| 1 | 1 | 1 | a[0] > a[1] | |
| 1 | 1 | 2 | a[1] > a[2] | |
| 1 | 1 | 3 | a[2] > a[3] | |
| 1 | 1 | 4 | a[3] > a[4] | |
| 1 | 1 | 5 | a[4] > a[5] | |
| 1 | 1 | 6 | a[5] > a[6] |
5. 插入排序
int insertValue = array[j];
int k = j - gap;
while (k >= 0 && array[k] > insertValue) {
array[k + gap] = array[k];
k -= gap;
}
array[k + gap] = insertValue;
具体解释详见《 Java 插入排序》
三、完整执行流程
处理前：{3, 32, 1, 55, 0, 3, 9} gap = 3, i = 0, j = 6, a[0] > a[6]，插入排序结果如下： 处理后：{3, 32, 1, 9, 0, 3, 55}gap = 3, i = 1, j = 4, a[1] > a[4]，插入排序结果如下： 处理后：{3, 0, 1, 9, 32, 3, 55}
gap = 1, i = 0, j = 1, a[0] > a[1]，即 3 > 0，插入排序结果如下： 处理后：{0, 3, 1, 9, 32, 3, 55}
gap = 1, i = 1, j = 2, a[1] > a[2]，即 3 > 1，插入排序结果如下： 处理后：{0, 1, 3, 9, 32, 3, 55}
gap = 1, i = 4, j = 5, a[4] > a[5]，即 32 > 3，插入排序结果如下： 处理前：{0, 1, 3, 3, 9, 32, 55}
四、时间、空间复杂度
时间复杂度：平均O(nlogn)，最好情况O(n^1.3) ， 最坏情况O(n^2) 空间复杂度：O(1) 只需要一个缓存区五、参考资料：
《希尔排序 - 维基百科 》 《希尔排序 - 百度百科》 《大话数据结构》 9.6 希尔排序 《白话经典算法系列之三 希尔排序的实现》 《经典排序算法 - 希尔排序Shell sort》