希尔排序

import java.util.Arrays;




/**
 * 希尔排序:高级算法之一，书写逻辑简单
 * @author admin
 *
 */
public class ShellSort {
    public static void main(String[] args) {
        int [] tmp = new int []{9,7,5,3,1,8,6,4,2,0,12,3,4,5,2};
        int[] sort = sort(tmp);
        System.out.println(Arrays.toString(sort));
    }
    
    private static int []  sort( int [] arrs) {
        int len = arrs.length;
        int temp, gap = len/2;//增量（步长）：分组的数量,
        while(gap > 0){
            //循环遍历每个Gap中的数据并对每个组项做插入排序
            System.out.println(Arrays.toString(arrs));
            //对每个组项中进行插入排序
            for (int i = gap; i < arrs.length; i++) {
                temp = arrs[i]; //当前操作的数据：临沭数据
                int preIndex = i-gap; // 这里有两点作用： 1.控制步长，保证，每次按照指定的步长比较两个数大小2.作为递归的结束条件
                //对当前操作的数据在当前组项中找到插入的坐标，并将对应该坐标及其后面的数据后移一位
                while (preIndex >=0 && arrs[preIndex] > temp ) {
                    arrs[preIndex+gap]=arrs[preIndex]; 
                    preIndex-=gap;//递归控制
                }
                //将当前操作的数据放到找到的坐标的位置
                arrs[preIndex + gap] = temp; 
            }
            gap /= 2;
        }
        return arrs;    
    }
}