[关闭]
@liweiwei1419 2019-01-19T17:40:10.000000Z 字数 3094 阅读 1297

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

插入排序 算法




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

“插入排序”算法的思想

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

image-20190111202752126

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

例如:把数字 ,插入到 ,我们看数组的方向是从末尾到开始:

先看到 ,比 大,继续看前一个数;

再看到 ,比 大,继续看前一个数;

在看到 ,比 大,继续看前一个数;

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

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

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

实现1:“逐个交换”版

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

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

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

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

2、内层循环的方向“从末尾到开头”,为什么不能取到 “”?

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

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

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

实现2:“挨个后退,留出空位”版

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

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

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

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

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

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

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

image-20190113115706261

image-20190113115522121

image-20190113115613344

时间复杂度与空间复杂度

时间复杂度:

分析:第 1 轮在最坏情况下要看 个元素;

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

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

……

轮在最坏情况下要看 个元素;

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

空间复杂度:

分析:我们在交换两个数组元素位置的时候,使用了 个辅助的空间。

尝试

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

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

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

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

总结

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

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

扩展

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

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

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

image-20190111213935955

image-20190111214009731

image-20190111214029269

(完)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注