初始时，有一个大小为 10 的无序序列。

在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。 接下来，按照直接插入排序的方法对每个组进行排序。 在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。 按照直接插入排序的方法对每个组进行排序。 在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。 按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。 需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。 所以，希尔排序是不稳定的算法。

package com.lifeibigdata.fight;/** * Created by lifei on 16/10/24. */public class ShellSort {    static int[] shellSort(int[] a){        int gap = a.length / 2;        while (gap >= 1){            // 把距离为 gap 的元素编为一个组，扫描所有组//            for (int i = gap; i < a.length; i++) {//                int j;//                int temp = a[i];                  //对距离为 gap 的元素组进行排序//                 for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {//TODO   j - gap//                     a[j + gap] = a[j];//TODO i - gap + gap//                 }//                 a[j + gap] = temp;//TODO   j - gap + gap = j//             }            for (int i = gap; i < a.length; i++) {                if (a[i] < a[i - gap]){// 2 0; 3  1;4  2;                    int tmp = a[i];                    a[i] = a[i - gap];                    a[i - gap] = tmp;                }            }            gap = gap /2;        }        return a;    }    public static void main(String[] args) {        int[] a = new int[]{9  ,  1   , 2  ,  5  ,  7  ,  4  ,  8  ,  6  ,  3   , 5};        int[] r = shellSort(a);        for (int x:r) {            System.out.println(x);        }    }}

直接插入排序和希尔排序的比较

直接插入排序是稳定的；而希尔排序是不稳定的。 直接插入排序更适合于原始记录基本有序的集合。 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。 在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。