插入排序

直接插入排序和二分插入排序

/**
 * @Author leijs
 * @date 2021/8/16
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 6, 8, 4, 9, 6, 2};
        int[] arr1 = insertSort(arr);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i]);
        }
        System.out.println();
        int[] arr2 = insertSortWithBinarySearch(arr);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i]);
        }
    }
    /**
     * 直接插入排序，时间复杂度O(n^2)，空间复杂夫O(1)
     * 可以理解为打扑克牌的摸牌按照顺序放牌的位置
     *
     * @param arr
     * @return
     */
    public static int[] insertSort(int[] arr) {
        // 从第一个元素开始作为插入排序，和前面排好序的元素比较找到插入位置
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            // 在前面排好序的数组找到插入位置
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) {
                    // 元素向后移动
                    arr[j + 1] = arr[j];
                } else {
                    // 找到元素的插入位置结束
                    arr[j + 1] = temp;
                    break;
                }
            }
        }
        return arr;
    }
    /**
     * 二分法插入排序
     * 含义：在插入第i个元素的时候，对前面0~i-1元素进行折半，先跟中间元素进行比较，如果小，则对前半在进行折半
     * 直到left<right,然后再把第i个元素前1位与目标元素之间的所有元素后移，再把第i个元素放在目标位置上
     */
    public static int[] insertSortWithBinarySearch(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            // 要插入的元素
            int temp = arr[i];
            int left = 0;
            int right = i - 1;
            int mid = 0;
            while (left <= right) {
                // 中间位置
                mid = left + (right - left) / 2;
                // 找到新的左坐标和右坐标
                if (arr[mid] > temp) {
                    // 说明要往左
                    right = mid - 1;
                } else {
                    // 说明要往右
                    left = mid + 1;
                }
            }
            // 大于temp的元素向右移动,只需要关注left->当前i之间的元素
            for (int j = i - 1; j >= left; j--) {
                // 其实就是left->i之间的元素
                arr[j + 1] = arr[j];
            }
            // 插入元素
            arr[left] = temp;
        }
        return arr;
    }
}

希尔排序

/**
 * @Author leijs
 * @date 2021/8/16
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 6, 8, 4, 9, 6, 2};
        int[] arr1 = shellSort(arr);
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i]);
        }
    }
    /**
     * 又叫“缩小增量排序”
     * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组
     * 所有距离为d1倍数的记录在同一个组中。
     * 先在各组内进行直接插入排序，然后，取第二个增量d2
     *
     * @param arr
     */
    public static int[] shellSort(int[] arr) {
        int length = arr.length;
        // 第一个循环决定比较的间隔
        for (int i = length / 2; i > 0; i = i / 2) {
            // 第二个循环根据间隔，将整个数组分为若干个数组
            for (int j = i; j < length; j++) {
                // 第三个循环，在子数组内进行插入排序算法
                for (int k = j; k >= i && arr[k] < arr[k - i]; k = k - i) {
                    int temp = arr[k];
                    arr[k] = arr[k - i];
                    arr[k - i] = temp;
                }
            }
        }
        return arr;
    }
}