动画：面试官问我插入排序和冒泡排序哪个更牛逼？

偏执的太偏执、 2023-06-20 06:09 7阅读 0赞

![format_png][]

作者 | 小鹿同学

来源 | 小鹿动画学编程

**写在前边**

![format_png 1][]

排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。

那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？

**思维导图**

![format_png 1][]

![format_png 2][]

**如何分析一个排序算法？**

之前写的一篇很详细的文章。

[佩奇学编程 | 复杂度分析原来这么简单][Link 1]

分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

**1.1 时间效率**

这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

**1.2 空间消耗**

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。

注意：是额外的内存空间，存储排序数据消耗的空间不计。

**1.3 稳定性**

算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

**什么是插入排序？**

顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。

![format_png 3][]

**如何实现插入排序？**

上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？

![format_png 4][]

首先我们要将数据划分为两个区间，已排序区间和未排序区间。

![format_png 5][]

![format_png 6][]

我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。

![format_png 7][]

![format_png 8][]

如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。

![format_png 9][]

![format_png 10][]

最后我们看一下总的插入排序动画和代码实现。

![format_png 11][]

**插入排序的性能**

我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。

**4.1 插入排序的稳定性**

再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

**4.2 插入排序的空间消耗**

我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。

**4.3 插入排序的时间效率**

插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。

如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n²)。

对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n²)。

小结

我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。

元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。

如果觉得写的有帮助，欢迎转发朋友圈圈哦！

![音符][format_png 12]

**有热门推荐????**

1.【程序员】[我们就必须承认：这个世界上，有很多问题，就是无解的][Link 2]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了！][Link 3]

![format_png 13][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNNUQwOUhZQW00cE5pY3dvNE00bGliSXJlMVBtZFRwc0o4VHZFUkpBckt0SFpJbFU1bVNGaklES0EvNjQwP3d4X2ZtdD1wbmc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9nOWlhVmlhZjNlTVFqTGdSUzVCYzIwWFQzRFZsMWFqbm1KdnlXR2dVOEFXa3ZmTk1XdEIzWDB1V3lyWUtsY25nVHo1dElNYUtHdVRoYVVUOXlaaWNyUU1vdy82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNNFdxektmSDM1cEVPYVVaRmFxcXZ2cDVXZDZueHlibXVqa2doaWJWTmliZ2ZoUGljZlhzNm1ZbEtRLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIwODg1OTkzNw%3D%3D&chksm=977de245a00a6b531acc38b224d113fa3405f18cb8cd71013c7b4dcb7922ecf98394bf528c84&idx=1&mid=2247484427&scene=21&sn=0ce7de439699dd3169ed8488cb5cd659#wechat_redirect
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNMDREcW5pY2lha0ZpYnVibUtpYVVtRVhtU3laZ2RiUElUUjdHUkhMbFEzVDdsZzJ2MEdRYkNCeGxHUS82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNbXZud3JCVjNoQUNBN3FtcElGZjZkaWJCcnhLMFR0bWc4b1B4RklsVVd3SXZIWmVHNUx5aWFuQkEvNjQwP3d4X2ZtdD1wbmc?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNVXEzWWliRDh2RzBNaWI3VGlheFR4d21Xc3BpY2dGYzcwdkVQMzVjU0NIUFVEbDdQVjl0cWRwS24yUS82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNMFA2OGZOakFwY0UzR1I0c0ptek9WNENjckJSaWF3N09pY0d1UHdnRnRwdEZBczdwSG9Ua3VBVVEvNjQwP3d4X2ZtdD1wbmc?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNZUZEY0p1ZHdZMTBscEFRSkxXUmZsZ25HYUQ1RkhGNm4wT2ljbjEzcGFWbUJpYUppYkpocXprdG9RLzY0MD93eF9mbXQ9Z2lm?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNVTlpYXlhWkJpYXg0ZkVsaGFpYnJMOGM4NGYyTUFiUUlrZGljMmlid3g2d3ozYlRKemJkZDA5RlV5T0EvNjQwP3d4X2ZtdD1wbmc?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNT0VoSVBuUWU5YXM4TzNVZFcxTkZNWXBxRlZNNTA4dnhOekt5Yno3Nm1VVko3d1RpYTA1Y3l4Zy82NDA_d3hfZm10PWdpZg?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNclVWS3QweWliQW9GSWtwcDdHdlpIdmp4ZFdFbkZOTnFyb0pOUXF2WWFreGgwdFhSaGJKb3NSdy82NDA_d3hfZm10PXBuZw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9vdXZmOGt6OGlhQXZLaWNMUEM0RzhJaFJ0MG9KSEFyQ3lNb2liS2lhazcxOGlhNUNyNktJWWdIZlJ3bWdTUDlXc1BpY0h2c211SERYaWEzZnJwa2liNnVYb3Z4YVJRLzY0MD93eF9mbXQ9cG5n?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6L2NaVjJoUnB1QVBpYUpRWFdHeUM5d3JVeklpY2liZ1hheXJnaWJUWWFyVDNBMXl6dHRidGFPMEpsVjIxd01xcm9HWVQzUXRQcTJDN0hNWXN2aWNTQjJwN2RUQmcvNjQwPw?x-oss-process=image/format,png
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/100978627
[GitHub]: https://blog.csdn.net/kexuanxiu1163/article/details/100137152
[KMP]: https://blog.csdn.net/kexuanxiu1163/article/details/97071390
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/103051357
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVR1U2ljRUtJcWdpYU9FdG9KaWEwTGcxYTJkWkVLcXlwYzlFcDUzVkpsb0Vobzg4VkdYeVpFSHB2d1paVXR6VnR2RTVJRWliQU5kbFdwUVJRLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png