【算法日积月累】2-插入排序

插入排序 算法

前面，我们看到了“选择排序”虽然好，但是有点死板。而我们在这一节介绍的“插入排序”是一个比“选择排序”聪明一些的算法，同时也是一个非常重要的排序算法，我们一定要掌握它。

“插入排序”算法的思想

下面是经典的《算法导论》（第 3 版）介绍“插入排序”的插图，很好地解释了“插入排序”的思想。

“插入排序”算法的思想是：把一个“新数”插入到一个“有序”的数组中，使之成为一个比原始“有序”数组多 1 个元素的“有序”数组，每一轮我们看数组的方向是从末尾到开始。

例如：把数字 $8$ ，插入到 $[1,3,5,7,9,12,15]$，我们看数组的方向是从末尾到开始：

先看到 $15​$，比 $8​$ 大，继续看前一个数；

再看到 $12$，比 $8$ 大，继续看前一个数；

在看到 $9$，比 $8$ 大，继续看前一个数；

在看到 $7$，比 $8$ 小 ，不用再看前面的数了，因为它们都比 $7$ 小，也肯定比 $8$ 小。

算法的思想很清楚了，下面就要考虑实现了。因为我们是在数组中进行操作，我们不能直接把 $8$ 插入到 $9$ 之前，我们采取的第 1 个策略是，从末尾到开头，只要前面的数比 $8$ 大的，就直接交换到前面。直到看到一个数等于或者小于 $8$（思考为什么可以“等于”）的时候，停止。第 2 个策略其实更加符合我们在生活中的做法，干脆我先让 $8$ “靠边站”（或者说“找到地方等着”），前面的数，从末尾到开始，只要比 $8$ 大的，就后退一格，最后一定会空出一个位置来，我们就把 $8$ 放在这个空出来的位置就好了。

“插入排序”算法的两种实现

实现1：“逐个交换”版

def insert_sort_1(nums):
    """
    插入排序第 1 版：相比选择排序而言，插入排序的内层循环可以提前终止。
    但是这个版本有个缺点，交换次数太多，每一次交换其实意味着 3 次赋值。
    优化的方向，逐个平移，最终赋值。
    :param nums:
    :return:
    """
    l = len(nums)
    for i in range(1, l):
        for j in range(i, 0, -1):
            # 只要前面的比后面的“严格”大，就要交换它们的位置
            if nums[j - 1] > nums[j]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break

编写代码的过程中，要特别注意“边界”，思考：

1、外层循环为什么从索引 $1$ 开始？

因为刚开始的时候，只有 $1$ 个数。只有 $1$ 个数的数组就是有序数组。

2、内层循环的方向“从末尾到开头”，为什么不能取到 “$0$”？

索引 $0$ 没有前面的元素了，如果取到 $0$，代码 nums[j], nums[j - 1] = nums[j - 1], nums[j] 就会抛出数组越界异常，这一点初学的时候，比较容易疏忽。

从这个代码中，其实我们可以看出“插入排序”比“选择排序”聪明的地方，在内层循环里，有个 break，这个 break 出现得越早，比较的次数就会越少，之前的那些数都不用看了。

再想想在“选择排序”那一节提到的特殊测试用例，对于“已经有序”的数组，为什么“插入排序”比“选择排序”要聪明。

实现2：“挨个后退，留出空位”版

def insert_sort_2(nums):
    """
    :param nums:
    :return:
    """
    l = len(nums)
    for i in range(1, l):
        # 每一轮先让这个元素去别的地方休息一下
        temp = nums[i]
        # 从 i 的前一个元素开始看
        j = i - 1
        while j >= 0 and nums[j] > temp:
            nums[j + 1] = nums[j]
            j -= 1
        # 因为已经看到 j 这个元素小于等于 temp 了
        # 因此空出来的位置是 j + 1，要把 temp 放在这里
        nums[j + 1] = temp

说明：1、实现这个版本的插入排序，刚开始并不是很容易一下子就写正确，难点还是在于一些边界条件，我把这些容易忽略的边界条件作为注释都写在了上面的代码中。

2、实现这个版本的插入排序比较容易出错的地方在于，这里没有交换操作，如果编写不正确，很有可能错误地“修改”了数组的元素，使之有序，这也是我曾经犯下的错误。特别注意 nums[j + 1] = temp，如果你写成 nums[j] = temp ，此时 temp 没有到“空位”坐下，而是覆盖了一个元素，这是导致算法错误的原因，你最后得到的数组是可能有序的，但是数组中的绝大多数元素，都不是刚开始的样子了。

而第 1 版的快速排序就没有这种风险，因为在第 1 版的快速排序中，只有交换元素的操作。

这里不要忘记了，当你写的代码似乎“不怎么听话”的时候，不妨像上一节一样，在程序中添加一些打印输出，看一看到底是哪里出错了。

代码不一定都得是我上面写的那个样子，只要你的思路是按照“插入排序”的思想来的，怎么写其实就是大同小异了，我在一遍又一遍写“插入排序”的时候，写出来的代码还不一样呢。

下面附上我以前的笔记，只是想说明刚开始写“插入排序”会遇到一些问题，一定要有耐心调试代码，并且总结。

时间复杂度与空间复杂度

时间复杂度：$O(n^2)$

分析：第 1 轮在最坏情况下要看 $1​$ 个元素；

第 2 轮在最坏情况下要看 $2$ 个元素；

第 3 轮在最坏情况下要看 $3$ 个元素；

……

第 $n$ 轮在最坏情况下要看 $n$ 个元素；

对它们求和，用等差数列的通项公式。不过其实你也不用计算它，“时间复杂度”的计算我们只看次数最高的，所以“选择排序”是平方时间复杂度。

空间复杂度：$O(1)$

分析：我们在交换两个数组元素位置的时候，使用了 $1​$ 个辅助的空间。

尝试

我们已经有两个排序算法了，还记得我们在第 1 节的时候留下的练习吗。拿你编写好的测试用例，比较一下“选择排序”与“插入排序”在数组元素“几乎有序”，或者就用极端情况，把一个有序的数组分别拿给“选择排序”与“插入排序”，看看哪个算法运行得准确，且更快。

“算法”的正确性应该是排在第 1 位的，“插入排序”虽然看起来比“选择排序”聪明一点，但如果编写不当，错误的“插入排序”算法是没有价值的。

我们对算法的正确性的检验，不能像以前一样，只基于自己手写的、小规模的数组，应该编写一些较大规模的测试用例，并且测试用例也用程序编写，这样编写出来的程序才能既正确，且“经得住考验”；

“选择排序”也不是没有用武之地，正如我们上一节末尾对“选择排序”的总结，“选择排序”的交换次数是最少，想想“插入排序”的两个版本实现，都避免不了大量的“交换”或者“移动”元素，想想那个给集装箱排序的例子。

总结

通过这一节的学习，我们要重点理解“插入排序”比“选择排序”智能的地方：“插入排序”的内层循环可以提前终止，而“选择排序”只能“傻乎乎”地把剩下没有排定的元素都比较一遍。

学习了“插入排序”，我们看到了算法的威力，我们的只是把算法修改了一点，就能让“算法”更聪明一点。后面我们会看到“插入排序”对于小规模的排序任务而言，它的表现出色，原因很简单，小规模的排序任务比起大规模的排序任务而言，“几乎有序”的概率更大一些。

扩展

1、还有一种可以“提前终止”的排序算法，名为“冒泡排序”，名字可以说很形象了。可以作为练习写一下“冒泡排序”。

2、“插入排序”有一点比较“傻”，就是如果“已经有序”的数组是 [3,5,6,7,...,3000]，中间的 “...” 表示省略了 2990 多个数，待插入的数字是 “4”，那么此时，要“移动”的次数就很多了，“5” 以后的元素全部都要后移一位。那么有没有一种排序算法可以较早地发现“5”呢？有时间的话，可以了解一下 shell 排序。

下面是以前学习 shell 排序的笔记：

（完）