欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

希尔排序

程序员文章站 2022-07-10 21:14:47
...
希尔排序思路概括来说是:分组 + 插入排序.

/**
     * 希尔排序
     * 思路:希尔排序,是缩小增量排序, 需要分组. 对每个分组实行直接插入排序.
     * 最好的情况:O(nlog2n)
     * 最坏的情况:O(n ^ 2)
     * 不稳定
     * 使用情况:中等大小规模
     */
    @Test
    public void testShellSort(){
        int[] arr = {4,2,5,1,2,9,8,3,5,6,2,8};
        // 分组 + 直接插入排序.
        for(int i=arr.length / 2; i>0; i/=2){
            shellSort(arr, i);
        }
        System.out.println(Arrays.toString(arr));
    }

    public void shellSort(int[] arr, int d){
        for(int i=d; i<arr.length; i++){
            int temp = arr[i];
            int j;
            for(j=i-d; j>=0; j-=d){
                if(temp < arr[j]){
                    arr[j+d] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+d] = temp;
        }
    }