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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
8 t" E( r$ [9 K, w. }
  c0 V! h' V+ |7 y写在前边
1 ?4 k6 M" ?3 r; [
. ]6 ?/ S2 A7 X3 \
6 C6 C  d6 p  ~* W, @6 w' t排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

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

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

思维导图

  N3 k& m; @3 H

- M5 w; b$ q. q
1

& P  e  v! d7 c1 P7 a$ {) p8 _" c3 ^如何分析一个排序算法？

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

2 n* |: F, D' Z/ }8 v佩奇学编程 | 复杂度分析原来这么简单
: R4 i% B+ W: ~) c& g2 r
分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

1.1 时间效率

, d. S5 I# n/ M, B. w这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
. c, W8 T" J. l0 z' K
. ^) j- t6 D7 _' d8 \" F, B/ s4 {, T3 J复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

3 t3 O' O& Y4 p9 V' @对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

1.2 空间消耗
# K& q0 F4 o$ _. Q3 a
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
: e" R& \" I* G3 t: D/ G* k
注意：是额外的内存空间，存储排序数据消耗的空间不计。

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

  {# d# s* b( S7 F4 Y$ d' b/ Z2
2 K1 C3 O2 E  R( D0 F
$ Z: g" F; _3 Q; I2 l0 |0 B什么是插入排序？

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


3
* z$ G# V0 I( v. z7 k0 \
+ G& t3 C1 J2 A如何实现插入排序？
+ U" n: s$ m+ f3 g
4 o2 q9 r3 O0 _& u, H9 U8 |6 l上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
  f( O! n5 Y2 ]0 x1 L' _

  j7 N8 `- s5 ?
% e8 H2 e9 w5 R首先我们要将数据划分为两个区间，已排序区间和未排序区间。

' p- ^( Y4 h- B8 k3 f
  N; C3 d% O2 B) {) J' \4 e

- e4 C, e9 m6 T; P$ ]/ r
- q) H& ?! K! r5 k4 y$ Z我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
$ j% A$ k2 x' X3 ?/ X2 [* ?




, P5 U' ~7 v7 F" M# ]如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
$ d- C7 Q# {5 }6 T+ J3 o9 z7 g

6 B( {7 `  _5 B  K


0 X0 p+ X4 N' H. x最后我们看一下总的插入排序动画和代码实现。

4 \' w' J: G& c, r) |: r

1 O9 s" e8 J/ t5 i4
! j, S  c: v2 F4 V
插入排序的性能
* y, \5 d  o/ X  s2 d
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
$ f0 ]+ Y, e5 s/ a2 \. @( s
. l( t" B: a# ?' e& m4.1 插入排序的稳定性

再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
, [, u7 P$ _. W0 N* `/ F
0 b, x' O  b/ i8 `4.2 插入排序的空间消耗
( G& K# ~5 C. _% L  C
+ V( \( ^9 l9 A$ L我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。

$ i8 U7 T" c" _( E* T/ k% l( y4.3 插入排序的时间效率

插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
" K/ |$ [8 u- u# l9 ^: g
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

1 H( m, `+ L# f对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

4 {7 y4 \! P# N+ w; S; M5
1 Y. \% \, v( Z8 Y
$ @# W" X- b6 S' c* v' J3 ~小结
+ R, L* u5 o) _9 Q9 a' k
" G* ^1 Z" V  l: w; P8 g( P8 `我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
1 k6 D- E* w3 I( L) ~+ A
  m0 E" E' ]; r# b" H4 O/ Y我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。

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

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

2 f/ |& j# H/ H9 }* A. u5 j' V虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
$ ~) S9 ]4 m; c, G0 {————————————————
0 b& ?5 x1 X1 M- _9 D  s2 _6 d* m版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# U) @2 @8 F1 C1 ^7 _" x原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708


( }8 N3 @1 f0 r/ X. M