上手难度：★★★★
算法复杂度：O(n^(1.3—2))
shell.gif
排序思想：
最开始以整个数组长度的一半作为步长gap进行分组；
例如8个元素，索引0和索引4一组，索引1和索引5一组，索引2和索引6一组，索引3和索引7一组，分别对分好的组使用插入排序进行排序，这样就得到了4个已经排好序的四组数据，
再对步长gap进行对半取值得到2，就会将索引0、索引2、索引4和索引6一组，索引1、索引3、索引5和索引7一组，再对这两组进行插入排序，就得到了两个排好序的数组；
再对步长gap进行对半取值得到1，就得到了一组数据，再对这一组数据进行插入排序，就能得出最终结果；
之所以没有一开始就进行插入排序，是因为，在大量数据面前，希尔排序通过对一个个分组进行排序，减少了比较和交换需要的次数，下图是10000个元素下插入排序和希尔排序的对比
代码实现：
public class ShellSort {
/**
* 插入排序，以gap为分组，往前进行比较
* 在gap为一半时，insert是每次对不同的分组进行操作
* 当gap为四分之一时，在i的自增和循环过程中，insert会先以四分之一的步长对前面的一部分进行排序，
* 然后再通过步长找到后面的值加入到前面的分组中，例如索引0、索引2、索引4和索引6一组，会先将索引0和2排好序，然后将4加入到0和2的数组中进行排序，这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
*/
private static void insert(int[] arr, int gap, int i){
int temp = arr[i];
//第一次进来i就等于gap的值，从gap开始往前比较
int j;
//插入的时候按组进行插入（组内元素两两相隔gap）
//这里循环的次数根据gap的值来确定，第一个gap等于整个数组长度的一半，这里只能循环一次，后面gap会慢慢按2等比缩小，循环的次数也多了，gap越小，分到的组员就越多
for(j = i - gap; j >= 0 && temp < arr[j]; j -= gap){
//将两两相隔gap的值进行比较，如果前一个值大于temp，就把前面的值赋给后面的值
//之所以把这个加入到判断条件，是因为按照插入排序的思维，默认前面已经排好序了
// 事实也的确如此，因为最开始对半取到的gap，只会有两个值作为1组，然后排好这一组后，才会在i的自增中把后面的gap步长的值加入进来
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
//由于j已经自减了gap，此时j+gap是gap前面的值，等于是交换了元素位置，把小值换到前面了
}
private static void shellSort(int[] arr){
int n = arr.length;
//每次都对半取gap的值，以gap为步长进行分组
for(int gap = n/2; gap > 0; gap /= 2){
for(int i = gap; i < n; i++){
//对各个分组进行插入排序 这里会循环n-gap次，每一次的循环，都是以gap为步长找到组员进行排序
//这个循环的目的是以gap距离等比作为一组
insert(arr, gap, i);
}
}
}
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
shellSort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}
优点：
减少交换次数，比插入排序提高了效率，因为插入排序每次只比较一位，而希尔排序通过分组的形式，减少了比较次数
缺点：
反直觉，只适合计算机中使用
优化方式：
希尔排序的间隔序列不推荐用2的幂(1 2 4 8 16...)，因为这样直到间隔为1之前，
都不会将奇数位置与偶数位置的元素进行比较，这样是低效的。希尔自己认为可以用2的幂 - 1序列(1 3 7 15...)，后来又有文章建议用3x + 1(1 4 13 40 121...)，都是可以的。
public static void shellSort2(int[] arr){
int gap = 1;
while (gap < arr.length/3) {
gap = gap * 3 + 1;
}
// 当gap小于数组整个长度的三分之一时，就自增3倍并且加1
// 1 4 13 40这种增长模式
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
insert(arr, gap, i);
}
gap = (int) Math.floor(gap / 3);
}
}
