【基础算法】排序算法 —— 插入排序

一、算法原理

插入排序将数组分为已排序区间和未排序区间，初始已排序区间只有数组第1个元素，未排序区间从下标 1 开始到数组末尾。每次取未排序区间的第1个元素，将它插入已排序区间的合适位置，并保证已排序区间一直有序。重复这个过程，直到未排序区间为空，算法结束。

给有序数组（已排序区间）插入1个新元素，并保持数组有序，应该都很熟悉。下图演示了给有序数组 [1，5，8] 插入 3 的过程，首先找到 3 应该在的位置，再把这个位置之后的元素全部向后移动一位，最后将 3 放在这个位置。

示例：使用插入排序对数组 arr = [4，5，6，3，2，1] 从小到大排序。

第1次插入：

第2次插入：

第3次插入：

第4次插入：

第5次插入：

二、代码实现

实现一

/**
 * 插入排序，时间复杂度 O(n^2)，空间复杂度 O(1)，稳定
 *
 * @param arr 待排序数组
 */
public static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    for (int i = 1, len = arr.length; i < len; i++) { // 未排序区间
        int j = i;
        while (j > 0 && arr[j] < arr[j - 1]) { // 查找未排序区间第1个元素，在已排序区间的合适位置，并交换
            swap(arr, j, j - 1);
            j--;
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    if (i == j) {
        return;
    }
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

实现二：

/**
 * 插入排序，时间复杂度 O(n^2)，空间复杂度 O(1)，稳定
 *
 * @param arr 待排序数组
 */
public static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    for (int i = 1, len = arr.length; i < len; i++) { // 未排序区间
        int cur = arr[i]; // 未排序区间第1个元素
        // 在已排序区间查找要插入的位置
        int j = i - 1;
        for (; j >= 0; j--) {
            if (cur < arr[j]) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        // 插入数据
        arr[j + 1] = cur;
    }
}

private static void swap(int[] arr, int i, int j) {
    if (i == j) {
        return;
    }
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

三、算法评价

3.1 时间复杂度

最好时间复杂度：O(n)

最好情况下，要排序的数组已经是有序的，并不需要搬移任何数据。如果从后到前在已排序区间里查找插入位置，每次只需要比较一次就能确定插入的位置，而且不用做数据交换。所以这种情况下，最好时间复杂度为 O(n)。

最坏时间复杂度：O(n²)

最坏情况下，要排序的数组刚好是倒序排列的，每次插入都相当于在数组的第一个位置插入新元素，需要移动已排序区间的所有数据，所以最坏情况时间复杂度为 O(n²)。

平均时间复杂度：O(n²)

我们知道，在数组中插入一个数据的平均时间复杂度是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n²)。

3.2 空间复杂度

插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，是一个原地排序算法。

3.3 稳定性

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。