一.概述
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
在学习插入排序的时候，倒序将待排序的第一个数和前面已排序的数进行比较再往前插时，必须依次往前，效率较低。故可通过增加步长h来提高效率。
二.原理
1.选定一个增长量（步长）h，按照增长量h对数据进行分组；
2.对分好组的每一组数据为一轮，每一轮内进行插入排序；
3.按照规则减少增长量h，最后减为1，重复第二步操作
注：关于增长量h的确定好像不唯一，我看的黑马视频里是这样规定的：
初始值：int h=1
while(h h=2h+1; }
减小规则： h=h/2
要更简便一点，h初始值应该也可以直接令h=a.length/2
如图，假设输入数组为{9,1,2,5,7,4,8,6,3,5} ， 按照插入排序的思想，将数组分为已排序和未排序两部分。在插入排序中，当数组为初始状态时，将索引0处的数视为已排序，索引1到n-1为未排序部分。而在希尔排序中，索引为0的数依旧视为已排序，而由于未排序数字倒序向已排序数字进行比较时存在一个增长量（步长）h，所以初始状态时，索引h的数字为待排序数字。
第一轮：为了方便演示，令h的第一个值为5，即索引=5为最初的待排序数字也就是“4”。将4和与其距离h的已排序数比较，此时已排序数字为索引0处的“9” ，4<9，所以不进行插入。由于待排序数字每次倒序遍历时，要和已排序数字的距离为h的倍数，所以此时“4”只能和“9”比较。
第一个待排序数“4”比较结束，使用第二个待排序数字“8”向前遍历，数字“8”的索引为6，与其比较的数的索引为6-5=1，即数字“1”。1<8，不将8进行插入…同理进行后序排列。
第二轮，h为2，第一个待排序数字为索引=h=2的数，即“2”，2与索引为0的数“4”比较，2<4，所以2和4交换。…后面的同理
三.java代码实现
public class shell {
public static void sort(int[] a){
int n=a.length;
int h=1;
while(h=1){
for(int i=h;i=h;j-=h){
if(a[j-h]>a[j]){
swap(a,j-h,j);
}else{
break;
}
}
}
h=h/2;
}
}
public static void swap(int[] a,int i,int j){
int k=a[i];
a[i]=a[j];
a[j]=k;
}
public static void main(String[] args) {
int[]a={9,1,2,5,7,4,8,6,3,5};
sort(a);
System.out.println(Arrays.toString(a));
}
}
运行结果：[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
需要注意的地方：
- 和基本的插入排序一样，外层循环i即待排序数，待排序数依次往后至最后一个数，所以i
- for内层循环时比较的是待排序数a[j]和a[j-h]，所以j=i，而h>=j。而待排序数向前比较时，每次跨越的步长为h，所以j=j-h。
- h减少规则在while循环内，for循环外。
这段代码可能没有那么简洁，但对于我这种初学者来说能理解就行。
第一次动手写博客，感觉的确能让自己更专注的去思考，有助于学习。
