Insertion Sort - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

5分钟搞定插入排序法 演算法 -- 六種排序法之二：插入排序法（insertion sort）

图解

详解

插入排序--直接插入排序 插入排序（图解） 插入排序及时间复杂度分析

标准写法

步骤1: 两层循环

• 外层循环：需要比较的轮数，从第二个数开始，把N个数进行N-1轮排序，当前轮的元素记作n
• 内层循环：在当前轮中，遍历该轮元素n前的每一个元素并比较

public static void insertionSort(int[] arr) {

    for (int i = 1; i < arr.length; i++) {
        for (int j = i; j >= 0; j--) {

        }
    }
}

步骤2: 移动元素并交换

public static void insertionSort(int[] arr) {

    int temp = 0;

    for (int i = 1; i < arr.length; i++) {
        // 记录当前轮的元素
        temp = arr[i];
        for (int j = i; j >= 0; j--) {
            if (j > 0 && arr[j - 1] > temp) {
                // 把元素往后移动一个位置
                arr[j] = arr[j - 1];
            } else {
                // 移动结束后，或到第一个元素后，前面记录的值覆盖到移动结束后的位置
                arr[j] = temp;
                break;
            }
        }
    }
}

要点

• 把N个数进行N-1轮排序，注意是"轮"
• 既可以升序排序，也可以降序排序，把if中的交换两个数的条件 arr[j - 1] > temp 改为 arr[j - 1] < temp 即可
• 最好时间复杂度是O(n)：已排好序；平均时间复杂度是O(n^2)；最坏时间复杂度是O(n^2)：倒序
• 空间复杂度O(1)