希尔排序

希尔排序

希尔排序又称”缩小增量排序”,是插入排序的优化,插入排序在少量数据或部分有序的情况下,非常高效,因此希尔排序通过适当构造满足前述的条件,让整个排序过程处理的比插入排序更优

    /**
     * 希尔排序
     * 步骤: 将数组分隔为h个间隔序列,例如:数组1~6分隔为[1,3][2,4][3,6],每个间隔序列相当于一个子数组,
     *       使用插入排序对子数组排序,然后减小h的值重新分割排序,当h为1时,数组和子数组相同,排序完成
     * 概述: 希尔排序权衡了子数组的规模和有序性,排序之初,各个子数组都很短;排序之后,子数组长但是部分有序
     *       这两种情况都很适合插入排序
     */
    public void shell(int[] arr){
        int len = arr.length;
        int h = 1;
        //设置间隔序列
        while(len/3>h)
            h = 3*h+1;
        //使用插入排序对每个间隔序列进行排序
        while(h > 0){
            for(int i=h;i<len;++i){
                for(int j=i;j>=h && arr[j] < arr[j-h];j-=h){
                    //交换
                    arr[j] = arr[j]^arr[j-h];
                    arr[j-h] = arr[j]^arr[j-h];
                    arr[j] = arr[j]^arr[j-h];
                }
            }

            h /= 3;
        }
    }