运用逆向思维：插入排序

labuladong原创约 1247 字

前置知识

阅读本文前，你需要先学习：

一句话总结

插入排序是基于选择排序的一种优化，将 nums[sortedIndex] 插入到左侧的有序数组中。对于有序度较高的数组，插入排序的效率比较高。

你可以点开可视化面板，点击播放按钮，然后点击加速/减速按钮调节速度，即可直观感受插入排序的过程：

前文选择排序所面临的问题中分析了选择排序遇到的几个问题，然后逐步优化写出了冒泡排序，使得排序算法具有稳定性，且能够在输入数组的有序度较高时提前终止，提升效率。

回顾一下，冒泡排序的关键点在于对下面这段代码的优化：

// 对选择排序进行第一波优化，获得了稳定性
void sort(int[] nums) {
    int n = nums.length;
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 在未排序部分中找到最小值 nums[minIndex]
        int minIndex = sortedIndex;
        for (int i = sortedIndex + 1; i < n; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }

        // 将 nums[minIndex] 插入到 nums[sortedIndex] 的位置
        // 将 nums[sortedIndex..minIndex] 的元素整体向后移动一位
        int minVal = nums[minIndex];
        // 数组搬移数据的操作
        for (int i = minIndex; i > sortedIndex; i--) {
            // swap(nums[i], nums[i - 1])
            nums[i] = nums[i - 1];
        }
        nums[sortedIndex] = minVal;

        sortedIndex++;
    }
}

为了避免 while 内存在两个 for 循环，我们使用了一种类似冒泡的方式逐步交换 nums[sortedIndex..] 中的逆序对，将最小值换到 nums[sortedIndex] 的位置。

好的，先停在这一步，让我们忘记冒泡排序的优化方法，你来思考一下，是否还有其他方法能够优化上述代码，把 while 循环中的两个 for 循环优化成一个 for 循环？

反向思维

上面的算法思路是：在 nums[sortedIndex..] 中找到最小值，然后将其插入到 nums[sortedIndex] 的位置。

那么我们能不能反过来想，在 nums[0..sortedIndex-1] 这个部分有序的数组中，找到 nums[sortedIndex] 应该插入的位置，然后进行插入呢？

当年我思考如何对插入排序进行优化时，是想到过这个思路的，因为我想利用数组的有序性呀：既然 nums[0..sortedIndex-1] 这部分是已经排好序的，那么我就可以用二分搜索来寻找 nums[sortedIndex] 应该插入的位置。

这样一来，上述代码中的内层第一个 for 循环，我可以给他优化成对数级别的复杂度。

但是仔细想想，用二分搜索好像是多此一举的。因为就算我用二分搜索找到了 nums[sortedIndex] 应该插入的位置，我还是需要搬移元素进行插入，那还不如一边遍历一遍交换元素的方法简单高效呢：

// 对选择排序进一步优化，想左侧有序数组中插入元素
// 这个算法有另一个名字，叫做插入排序
void sort(int[] nums) {
    int n = nums.length;
    // 维护 [0, sortedIndex) 是有序数组
    int sortedIndex = 0;
    while (sortedIndex < n) {
        // 将 nums[sortedIndex] 插入到有序数组 [0, sortedIndex) 中
        for (int i = sortedIndex; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                // swap(nums[i], nums[i - 1])
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
            } else {
                break;
            }
        }
        sortedIndex++;
    }
}

插入排序

这个算法的名字叫做插入排序，它的执行过程就像是打扑克牌时，将新抓到的牌插入到手中已经排好序的牌中。

插入排序的空间复杂度是 $O(1)$ ，是原地排序算法。时间复杂度是 $O(n^2)$ ，具体的操作次数和选择排序类似，是一个等差数列求和，大约是 $n^2/2$ 次。

插入排序是一种稳定排序，因为只有在 nums[i] < nums[i - 1] 的情况下才会交换元素，所以相同元素的相对位置不会发生改变。

初始有序度越高，效率越高

显然，插入排序的效率和输入数组的有序度有很大关系，可以举极端例子来理解：

如果输入数组已经有序，或者仅有个别元素逆序，那么插入排序的内层 for 循环几乎不需要执行元素交换，所以时间复杂度接近 $O(n)$ 。

如果输入的数组是完全逆序的，那么插入排序的效率就会很低，内层 for 循环每次都要对 nums[0..sortedIndex-1] 的所有元素进行交换，算法的总时间复杂度就接近 $O(n^2)$ 。

如果对比插入排序和冒泡排序，插入排序的综合性能应该要高于冒泡排序。

直观地说，插入排序的内层 for 循环，只需要对 sortedIndex 左侧 nums[0..sortedIndex-1] 这部分有序数组进行遍历和元素交换，大部分非极端情况下，可能不需要遍历完 nums[0..sortedIndex-1] 的所有元素；而冒泡排序的内层 for 循环，每次都需要遍历sortedIndex 右侧 nums[sortedIndex..] 的所有元素。

所以冒泡排序的操作数大约是 $n^2/2$ ，而插入排序的操作数会小于 $n^2/2$ 。

你可以把插入排序的代码拿去力扣第 912 题「排序数组」提交，它最终依然会超时，但可以说明算法代码的逻辑是正确的。之后的文章我们继续探讨如何对排序算法进行优化。

运用逆向思维：插入排序

912. 排序数组 https://leetcode.cn/problems/sort-an-array

912. Sort an Array https://leetcode.com/problems/sort-an-array

反向思维

初始有序度越高，效率越高