原理

首先将数组两两分组，分成n组数组，每组数组内部进行排序。再分成n/2组数组，每组数组内部进行排序。直至分成只剩一组，最后进行排序得到最后的数组。

代码

public static int[] shell(int[] arr) {
	 int temp;
	 for (int gra = arr.length/2;  gra>0; gra = gra/2) {
		   for (int i = gra; i < arr.length; i++) {
			     for (int j = i - gra; j >= 0; j-=gra) {
				       if(arr[j] > arr[j+gra]){
					         temp = arr[j];
					         arr[j] = arr[j+gra];
					         arr[j+gra] = temp;
				       }
			     }
		   }
	 }
}

详细讲解

希尔排序复杂程度不高，他只是在其他排序算法上增加了分组的性质。
希尔排序最开始会以两个为一组进行分组，组数也叫增量，相隔增量的方式分组。

例如上图，一个数组（array） 八个数据，两两分组分为4组，增量（gra）也为4.
则分组原则就是 array[index] 和 array[index + gra] 为一组
下列的格式为：数值(下标)

第一组： 5(0)， 9(4)
第二组：12(1)，15(5)
第三组： 8(2)， 2(6)
第四组：20(3)，16(7)

每一组数值进行一次排序

1. 第一组顺序正确
2. 第二组顺序正确
3. 第三组调换顺序
4. 第四组调换顺序

接着组数减半，分为2组，增量也变为2

第一组：5(0)，2(2)，9(4) ，8(6)
第二组：12(1)，16(3)，15(5)，20(7)

1. 第一组进行排序得到：2，5，8，9
2. 第二组进行排序得到：12，15，16，20

接着组数减半，分为1组，增量也变为1，当增量为1时，表示为最后一次进行分组排序

只剩下一组数据：
2，12，5，15，8，16，9，20

进行最后的排序，得到最终的顺序。

备注

希尔排序分为两种：希尔冒泡排序 和 希尔插入排序
上边展示的代码为希尔冒泡排序，希尔插入排序代码如下

public static int[] shell(int[] arr) {
    for (intgra = arr.length/2;  gra>0; gra = gra/2) {
        for (int i = gra; i < arr.length; i++) {
            int temp = arr[i];
            int index = i;
            while(index - gra >= 0 && arr[index-gra] > temp) {
                arr[index] = arr[index-gra];
                index -= gra;
            }
            arr[index] = temp;
        }
    }
    return arr;
}

除了分组排序的方式改变了，大致原理相同。