希尔排序
希尔排序是升级版的插入排序，也叫缩小增量排序。
时间复杂度是O(nlog2n)，是不稳定的算法
1.如何确定增量
这里就用最简单的增量减半
2.代码如下：
public static void shellSort(int[] array){
int step = array.length;
//记录每个组里的第一个元素的下标
int i;
//遍历时记录组里元素的下标
int j;
//保存将要插入的那个值的（不是下标了）
int tem;
//保存插入时要比较的元素的下标
int k;
// 如何计算增量（增量同时也是组数）
while((step = step / 2) > 0){
//某个增量具有的组数，分别对不同组进行插入排序，搭配初始化时的变量解释看，这里step有多大，就有多少组需要进行插入排序
for(i = 0 ; i < step ; i++){
//这里开始插入排序，与一般的插入排序无异，只是原来的插入排序是变化1来进行比较插入，这里是变化step来进行比较插入
for(j = i + step ; j < array.length ; j = j + step){
//发现那个元素小于待插入元素时
if(array[j] < array[j - step]){
tem = array[j];
k = j - step;
//这里必须先写k>=0,因为k可能是负值，先写后边的可能会数组越界
//循环插入比较，直到遇到比待插入值大的数字
while(k >= 0 && tem < array[k]){
array[k + step] = array[k];
k = k - step;
}
//k是不满足上诉while循环的条件，所以k+step才是正确的插入位置，搞定。
array[k + step] = tem;
}
}
}
}
}
代码：
public class ShellSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public static void shellSort(int[] array){
int step = array.length;
int i;
int j;
int tem;
int k;
while((step = step / 2) > 0){// how much step
for(i = 0 ; i < step ; i++){//one step has step's group
for(j = i + step ; j < array.length ; j = j + step){
if(array[j] < array[j - step]){
tem = array[j];
k = j - step;
while(k >= 0 && tem < array[k]){
array[k + step] = array[k];
k = k - step;
}
array[k + step] = tem;
}
}
}
}
}
private static void print(int[] array){
for(int i : array){
System.out.print(i + " ");
}
System.out.println("");
}
}
