高级排序之希尔排序

1、什么是希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

2、原理

1、选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2、对分好组的每一组数据完成插入排序；
3、减小增长量，最小减为1，重复第二步操作。

4、增长量h的确定：增长量h的值没一固定的规则，我们这里采用以下规则：

int h=1 
while(h < 数组长度/2){    
	h=2h+1；//3,7 
} //循环结束后我们就可以确定h的大值； 
//h的减小规则为：    
	h=h/2

3、代码实现

public static void sort(int[] arr){
     //定义一个增长量h
     int h = 1;
     while ( h < arr.length/2){
         h = 2*h+1;
     }
     while (h >= 1){
         for (int i = h; i < arr.length; i++) {
             for (int j = i; j >= h; j=j-h) {
                 if (arr[j] < arr[j-h]){
                     int temp = arr[j];
                     arr[j] = arr[j-h];
                     arr[j-h] = temp;
                 }else {
                     break;
                 }
             }
         }
         h = h/2;
     }
 }