【插入排序】：直接插入排序、二分插入排序、shell排序

1. 直接插入排序

1.1 详细过程

1.2 代码实现

public static void swap(int[]arr,int a,int b){
        int tmp=arr[a];
        arr[a]=arr[b];
        arr[b]=tmp;
    }
    public static void sort(int[] arr,int left,int right){
        if(right>=arr.length) return;
        if(left>=right) return;
        if(arr[left]>arr[left+1]){
            swap(arr,left,left+1);
            sort(arr,0,left);
        }
        left++;
        sort(arr,left,right);
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,5,7,21,2,6,93,8};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

2. 二分插入排序

2.1 详细过程

2.2 代码实现

  public static int search(int[] arr, int left, int right, int key) {
        if (left > right) {
            // 没有找到key，返回应该插入的位置
            return left;
        }
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] > key) {
            return search(arr, left, mid - 1, key);
        } else {
            return search(arr, mid + 1, right, key);
        }
    }

    public static void sort(int[]arr){
        //遍历比较
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]<arr[i-1]){
                //进入二分查找
                int pos=search(arr,0,i-1,arr[i]);
                //目标位置集体往后移
                int tmp=arr[i];
                for(int j=i-1;j>=pos;j--){
                    arr[j+1]=arr[j];
                }
                //插入
                arr[pos]=tmp;
            }
            System.out.println("第"+i+"次: "+Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,56,88,66,35,2,8};
        sort(arr);
    }

3. shell排序

3.1 详细过程

3.2 代码实现

    public static void sort(int[] arr){
        int gap=arr.length/2;
        //开始遍历
        int j=1;
        do{
            for(int i=0;i<arr.length-gap;i++){
[video(video-SY1ydW46-1732779457803)(type-csdn)(url-https://live.csdn.net/v/embed/436204)(image-https://v-blog.csdnimg.cn/asset/26566b09687ce9bdc33dff17e9c146c4/cover/Cover0.jpg)(title-二分插入排序1)]

                if(arr[i]>arr[i+gap]){
                    //交换
                    int tmp=arr[i];
                    arr[i]=arr[i+gap];
                    arr[i+gap]=tmp;
                }
            }
            gap/=2;
            System.out.println("第"+j+++"次: "+Arrays.toString(arr));
        }while(gap>=1);
    }
    public static void main(String[] args) {
        int[] arr=new int[]{1,56,88,66,35,2,8};
        sort(arr);
    }