希尔排序

希尔排序就是变种插入排序算法 alt

将数据分成多个子表，先实现局部有序。

缩小距离组成第二个子表

alt

alt

第三趟

alt

当d=1时

alt

整个表呈现了基本有序，直接进行插入排序。

alt

总体 建议增量为 个数/2

alt

alt

算法实现

alt

如果 当前元素比前面的元素小需要把元素暂存到A[0]中。

相当于插入排序的变种，在插入排序的外层套了一层魂环。

    public static void main(String[] args) {
        int[] nums={49,38,35,32,65,55,43,90,76};
        int n=nums.length;
//        insertSort(nums,n);
        shellSort(nums,n);
        System.out.println(Arrays.toString(nums));

    }

    public static  void shellSort(int A[],int n){
        int i,j,d; //d用于记录间距
        //d是间距 每次缩小一半
        for (d=n/2;d>=1;d=d/2){
            //内层是插入排序
            for(i=d+1;i<=n;++i){
                if (A[i]<A[i-d]){
                 A[0]=A[i];
                    for(j=i-d;j>0 && A[j]>A[0];j-=d){
                        A[j+d]=A[j];
                    }
                    A[j+d]=A[0];
                }
            }
        }
    }

算法性能分析

alt

空间复杂度O(1)

时间复杂度最坏情况O（n**2）

稳定性

alt

总结

alt