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

杨利霞

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

7 T( _" U3 J$ u+ ]/ T1 A写在前边
1 u1 i0 Z1 c$ w3 N, O

排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
8 e, S: |" j3 [( c% Q
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
5 Z5 H% S. {( _& z: n1 d, ^
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？

思维导图


) K5 p& M% j$ K: k# a. x) K

1

如何分析一个排序算法？
, M2 m+ u* V) q5 f9 ?1 E
9 c; g# h9 V; q5 s) I9 l之前写的一篇很详细的文章。
2 L. v2 E8 M8 H: ^' ?
佩奇学编程 | 复杂度分析原来这么简单
6 D* I- p1 ~( H
- R+ V) O) N- }% j  L( o  u分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

1.1 时间效率
; ]# q/ J8 N9 C1 e  b( k
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
: e9 Q% |, f% M$ N- r' q
+ n  g4 q& m* z! L复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
: v( |7 `4 x8 l3 }5 ]' i
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

" R) o4 ?; h7 y9 G2 L* t1.2 空间消耗

/ i( L9 U7 b7 m6 Z0 w% l! K所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
. b. y& \' F8 ?& a7 }( ]: ~- }$ C
# m  u! M' C# N$ M注意：是额外的内存空间，存储排序数据消耗的空间不计。

+ J/ Q4 R5 v) G2 e1.3 稳定性
& n. P7 s5 N' C
2 h: I8 |  ]; a, j% N算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
- [  ]+ T5 P, A1 Y/ r3 t- Q
2
1 g, c3 m7 O) _* k- b
什么是插入排序？

+ Q$ Z, \/ ]' A; T* {8 f- C顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
+ d: R! j$ x5 c  ?6 n
7 |; r0 o9 l1 K" }( v1 W& G4 m+ |( X

3
0 x/ O/ d! e3 L' @
6 e9 Z' M7 I% v# `! q如何实现插入排序？
  C9 ~, S! S- a6 f6 H4 g" P, P
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？

$ I1 C8 N1 D1 b6 @& ^) ]

1 `. _( O3 G$ n" U  j# _首先我们要将数据划分为两个区间，已排序区间和未排序区间。

3 Q8 s; s2 c5 }; R  D$ P# x$ O5 N
; u6 c  q5 W3 c' D
) H* B9 g" H: U* ~

4 q0 d$ z, I: `( U3 a我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。

5 w. S0 K+ K& c/ v( b5 K9 }
6 r$ u9 [, M6 k) z$ _


如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
! ]& E6 k: k! X: e4 H& T6 O8 R/ n

6 P1 |. I9 ^7 R  C
7 O) U3 k3 o5 t  i4 _0 t; Q
/ ?/ H& l9 E; W
) a, }* x( p! p0 |- }: v5 Z6 i最后我们看一下总的插入排序动画和代码实现。
- _$ `* r0 r, J& N' V7 D
* R5 {  c2 `! p) f2 J* K4 T
8 M  j! D4 v6 e9 H, \* X
4
5 \" X, t" \8 l6 Q5 W* T
$ u: N5 M( {& ]& W6 v. {插入排序的性能

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

' ~% C0 p" L- T3 u0 q/ ?  O" _: i( K4.1 插入排序的稳定性
4 O7 L9 y; ^4 W3 Y
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
' O) L# m& |2 \. W* K1 l0 z
, p, ?  e7 ]& p4.2 插入排序的空间消耗

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

4.3 插入排序的时间效率
) o4 Z1 Z$ L* n* U2 C6 O- z
插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
1 ~* S# ^8 Z: Y- K/ S3 B
! L. {5 Q0 X( L& V( s/ X如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

! X4 [  t8 C! |1 h对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

6 ~1 _: r7 l8 ~. P9 O" s1 b! f5
8 `5 b  i) N& }. m3 m% y
小结
+ Z$ K& r& {4 S0 @: e
3 R) a- l# N# R$ k0 z我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
# v# O7 Y* n+ g. W2 M) d  j* p# R
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。

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

% ]& }( i2 B3 [- v1 M5 W  u有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
1 U% u% n1 t  h1 U& X' d
- D% a# a% F2 e虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
: Q& B8 ^9 X. y. N8 }6 U: b$ _7 ^( V: r
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
5 {. ^# J% p6 v, j版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
- [+ E: }0 P2 {( a/ M* D  w* [0 y6 E原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
9 `; g9 Y  O6 {2 g# Z) p
6 D2 Z& z5 V! l& ~1 }0 a3 O