算法与数据结构-希尔排序

思想：希尔排序就是简单插入排序的优化版本，以逐步递减步长，分序列进行插入排序，直至步长为1即是简单插入排序，即排序完成。

普通查找插入方式

public class DemoApplication {
    public static void main(String[] args) {
        int arr[] = {6, 4, 20, 9, 44, 11, 0,2,23,10,17,3};
        shellSort(arr);
        
        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + ",");
        }
    }
    //希尔排序
    public static void shellSort(int arr[]){
        int length = arr.length;
        for(int gap = length >> 1; gap > 0 ; gap >>= 1){
            for(int i = gap; i < length; i++){
                //普通插入算法
                int temp = arr[i];
                int j = i - gap;
                for(;j >=0 && arr[j] > temp; j -= gap){
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
            System.out.print(gap + "--");
            for(int k = 0; k < arr.length; k++){
                System.out.print(arr[k] + ",");
            }
            System.out.println();
        }
    }

 }

采用二分查找法插入

public class DemoApplication {
    public static void main(String[] args) {
        int arr[] = {6, 4, 8, 9, 2, 3, 1};
        shellSort(arr);
        
        for(int k = 0; k < arr.length; k++){
            System.out.print(arr[k] + ",");
        }
    }
    //希尔排序
    public static void shellSort(int arr[]){
        int length = arr.length;
        for(int gap = length >> 1; gap > 0 ; gap >>= 1){
            for(int i = gap; i < length; i++){
                int s = binarySearchGap(arr, gap,i - gap, arr[i]);
                if(s != -1){
                    int t = arr[i];
                    int j = i;
                    while(j > s){
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[s] = t;
                }
            }
            System.out.print(gap + "--");
            for(int k = 0; k < arr.length; k++){
                System.out.print(arr[k] + ",");
            }
            System.out.println();
        }
    }

    
    public static int binarySearchGap(int[] arr, int gap, int n, int target) {
        int left = 0;
        if(gap != 1){
            int t = n;
            while(t >= 0){
                left = t;
                t -= gap;
            }
        }
        int right = n;
        while(left <= right){
            int middle = (left + right) >> 1;
            if(gap != 1){
                //left+right除以2得到的下标可能不在以gap为间隔的序列中
                int t = left;
                boolean flag = false;
                while(t <= right){
                    if(t == middle){
                        flag = true;
                        break;
                    }
                    t+=gap;
                }
                if(!flag){
                    middle = left;
                }
            }
            if(arr[middle] > target){
                right = middle - gap;
            }else{
                left = middle + gap;
            }
        }
        return left <= n ? left : -1;
    }

 }

参考地址：排序算法(4) -- 希尔排序_Dby_freedom的博客-CSDN博客_希尔排序 步长为4