算法入门-排序算法-希尔排序-详解

一、核心思想

希尔排序可以看作是插入排序的改进版本，先理解插入排序有助于对希尔排序的理解

思想：将要排序的数组看作是由多个数组编织而成（即要排序的数组中是由多个子数组的元素交替排列而成的；同一子数组中元素间隔不同，则从原数组中拆分出来的子数组不同）；通过对每个子数组进行插入排序，得到一个近似有序的数组，在对近似有序数组进行插入排序即可得到最终有序数组。
举例：要排序的数组为 {1，5，3，9，6，4}，间隔为3时，可以看作是由{1，9}、{5，6}、{3，4}编织而成的

二、过程分析

通常初始设定间隔gap=nums.length/2生成初始子数组集，此后每次生成子数组集的间隔为gap=gap/2；
接下来对子数组进行插入排序即可

三、代码

    public void test10(){
        //将间隔为gap的元素分为一组，执行插入排序
        int[] nums=new int[]{1,5,3,9,6,4};
        int j;
        for(int gap=nums.length/2;gap>0;gap=gap/2){
            //以gap为间隔，对子数组集做插入排序
            for (int i=gap;i<nums.length;i++){        
                // 固定下来  与前面相隔gap的元素组成的数组做直接插入排序      
                int temp=nums[i];                          
                // 当前元素值小于前面的元素值则继续寻找， 不满足此条件的话说明当前元素大于前面的元素 符合我们的排序初衷 
                for (j=i;j>=gap&&nums[j-gap]>temp;j-=gap){  
                    // 把大于当前元素的元素 放在j位置（较大元素后移） 并将当前元素的索引（即j ）往前移动gap个单位
                    nums[j]=nums[j-gap];                    
                }
                // temp大于nums[j-gap]  说明temp找到了合适的位置
                nums[j]=temp;                               
            }
        }

        System.out.println(Arrays.toString(nums));
    }