版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/d3a12239d376
概念
希尔排序是插入类排序算法，它的本质就是分组插入排序，它采取分割策略：将相距某个“增量”的记录组成一个子序列，保证在每个子序列内部分别进行插入排序后得到的结果是基本有序。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比插入排序有大幅度提高。
Java实现
// 定义接口
interface Sorter {
/**
* 将数组按升序排序
*/
int[] sort(int[] arr);
/**
* 交换数组arr中的第i个位置和第j个位置的关键字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//希尔排序
public class ShellSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
shellSort(arr);
return arr;
}
// Shell排序的关键就是增量序列的选取：
// 增量序列原则： 增量序列的最后一个增量必须等于1
private void shellSort(int[] arr) {
int len = arr.length;
int increment = len;
for (; increment != 1;) {// 循环直至increment=1
increment = increment / 3 + 1; // 计算增量序列(将整个序列分成increment组,在组内进行插入排序)
for (int i = increment; i < len; i++) {
if (arr[i] < arr[i - increment]) {
int tmp = arr[i]; // 暂存arr[i]的值
int j;
for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {
// 组内记录后移,查找插入位置
arr[j + increment] = arr[j];
}
// 找到插入位置
arr[j + increment] = tmp;
}
}
}
}
}
演示
比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}
初始时increment=arr.length=9，increment != 1，执行第1次循环：
increment = 9/3+1 = 4，将整个序列分成4组，组内进行插入排序：
第 1 组： 9 3 2 -----------> 2 3 9
第 2 组： 1 7 -----------> 1 7
第 3 组： 5 4 -----------> 4 5
第 4 组： 8 6 -----------> 6 8
此时序列为 2 1 4 6 3 7 5 8 9
increment=4，increment != 1，执行第2次循环：
increment = 4/3+1 = 2，将整个序列分成2组，组内进行插入排序：
第 1 组： 2 4 3 5 9 -----------> 2 3 4 5 9
第 2 组： 1 6 7 8 -----------> 1 6 7 8
此时序列为 2 1 3 6 4 7 5 8 9
increment=2，increment != 1，执行第3次循环：
increment = 2/3+1 = 1，将整个序列分成1组，组内进行插入排序（演变为直接插入排序）：
第 1 组 ： 2 1 3 6 4 7 5 8 9 -----------> 1 2 3 4 5 6 7 8 9
increment=1，结束循环，排序完毕。
