插入排序

原理

将给定的数组从第一位开始，遍历，每取一位都和她前面的元素比较，前面的大，就把他放到当前元素后边，不断向前，知道前面的元素比后面小。

时间复杂度

O(nn)
最好情况On
最坏情况O(nn)

空间复杂度

O(1)

代码

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int t;
        for (int j = i; j >= 0; j--) {
            if (j > 0 && arr[j - 1] > tmp) {
                t = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = t;
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

可以化简为如下代码，不用特意进行交换，因为他每次往前飞，如果前面的都会覆盖当前的，每移动一次，覆盖一次，直到找到前面的元素比tmp小，则把那个元素赋值给tmp,这里可以用打断点追踪一下，很清晰，很巧妙！！！，思路起源于这篇博客，点击访问

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int t;
        for (int j = i; j >= 0; j--) {
            if (j > 0 && arr[j - 1] > tmp) {
                arr[j] = arr[j-1];
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

或者，条件变一下, 原理大同小异，下面的其实把条件从if里面移动到while里了

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        int insert = i;
            while (insert>0 && tmp<arr[insert-1]){
                arr[insert] = arr[insert-1];
                insert--;
            }
            arr[insert] = tmp;
    }
    System.out.println(Arrays.toString(arr));
}

希尔排序

原理

直接插入排序其实是希尔排序gap步长为1的特例

时间复杂度

O(nlog n)
最好情况O(nlog n)
最坏情况O(n*log^2 n)

空间复杂度

O(1)

代码

public static void shellSort(int[] arr){
    for (int gap = arr.length/2; gap >0 ; gap/=2) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            for (int j = i; j >= 0; j-=gap) {
                if (j-gap >= 0 && tmp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                } else {
                    arr[j] = tmp;
                    break;
                }
            }
        }
    }
}

或者

public static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int insert = i;
            while (insert - gap >= 0 && tmp < arr[insert - gap]) {
                arr[insert] = arr[insert - gap];
                insert -= gap;
            }
            arr[insert] = tmp;
        }
    }
}

或者

public static void shellSort(int[] arr) {
    int n = arr.length;

    // 初始的间隔取 n/2，然后每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 使用插入排序对每个分组进行排序
        for (int i = gap; i < n; i++) {
            int tmp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = tmp;
        }
    }

    System.out.println(Arrays.toString(arr));
}

参考文档

插入排序
知乎文章 八大排序算法