排序—插入排序

基本介绍

插入排序（Insertion Sort）是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。

代码实现

public class InsertSort {

    public static void insert(int[] arr) {
        int insertIndex = 0;
        int insertVal = 0;
        for (int i = 1; i < arr.length; i++) {
            // 待插入的数
            insertVal = arr[i];
            // arr[i]前面一个数的角标
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }
    
}

复杂度分析

最好的情况是，给定的数组已经排好序了，只需要进行 n-1 次比较，没有进行交换。时间复杂度为O(n)。

最坏的情况是，给定的数组逆序排列，时间复杂度为O(n^2)。