希尔排序

简单插入排序可能会出现的问题

显而易见，当大多数的数已经排序好，只有小的数在最后面的时候，插入排序的效率是非常低的。

希尔排序介绍

希尔排序是希尔于1959年题出的一种排序算法，希尔排序也是一种插入排序，他是简单插入
希尔排序是把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序

时间复杂度：O(nlogn)
稳定度：不稳定

思路：
1）将数组进行分组，
第一次分组 组数为 gap = arr.length/2,
接下来的分组 组数为 gap/2，循环直到组数为1
2）获得分组,只需遍历一半的元素，就可以获得再其中小组的成员
for(int i = gap;i<arr.length;i++) {
判断小组中成员的大小，小放前，大放后

交换法

/*
    * 交换法 速度慢(不推荐)
    * 里面实际上就是一个 分了组的冒泡排序
    */
   public static void shellSort(int[] arr) {
       int count = 0;
       int temp;
       //希尔排序的第一轮排序
       //因为第一轮排序，是将10个数据分成了5组
       for (int gap = arr.length / 2; gap > 0; gap /= 2) {
           //缺点：里面实际上就是一个冒泡排序
           for (int i = gap; i < arr.length; i++) {
               //遍历各组中所有的元素（共gap组，每组有arr.length/gap个元素），步长gap
               for (int j = i - gap; j >= 0; j -= gap) {
                   // 如果当前元素大于加上步长后的那个元素，说明交换
                   if (arr[j] > arr[j + gap]) {
                       temp = arr[j];
                       arr[j] = arr[j + gap];
                       arr[j + gap] = temp;
                   }
               }
           }
       }

   }

缩小增量法

	/**
     * 速度比交换法快，推荐
     * 思路：
     *      1）先进行分组
     *      2）然后循环每个分组，在分组中再进行插入排序
     */
    public void shellSort3(int[] arr) {
        //分组
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //每组进行插入排序
            for (int i = 0; i < gap; i++) {
                for (int j = i;j<arr.length - gap;j+=gap){
                    //要进行插入的元素
                    int insert = arr[j + gap];
                    //要插入的位置
                    int insetIndex = j;

                    while (insetIndex>=0 && insert < arr[insetIndex]) {
                        //将大数往后移动一位
                        arr[insetIndex + gap] = arr[insetIndex];
                        //指针前移
                        insetIndex -= gap;
                    }
                    //找到的插入的位置
                    arr[insetIndex+gap] = insert;
                }
            }
//            System.out.println("第"+(++count)+"轮:"+Arrays.toString(arr));
        }
    }