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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
  S1 ^3 w3 N9 Q
( X+ A; D( ~- ?- a写在前边


排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
5 I, M/ ]5 x8 S5 V3 X4 I
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
# B6 Y  d+ \& E8 v0 p( X
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
& R- e/ ~' A; C2 Y5 f& k+ a, Y( E) e, F5 B
, j4 {! {2 I8 t8 W4 s+ A' A/ v& e思维导图
- x  V. F# F9 g% f: E6 i


) r: g' w/ ?3 `: ~
1
3 H/ _5 g; |( \/ d- ^) O. E0 Z! U
如何分析一个排序算法？

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

; R2 b) }) e: c4 t% V佩奇学编程 | 复杂度分析原来这么简单
# v) R1 m/ u8 }  ^: e' ~1 y
5 f( \4 C0 l( o2 z分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
5 p! x6 L# r( z" P/ l3 m
+ `  p: Y; n; H0 I& ]  p/ \1.1 时间效率

' B* M: s( Z& i; p2 B6 j; y$ C这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
, T9 ^% T4 ^. J- q9 c
. M8 l- J9 h+ P/ @4 |# `复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

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

) ^& B  X1 V1 Q. y" M+ z1.2 空间消耗
. X. D6 [$ k& p' I. q" C$ L- h
% \& A  D9 Q9 o2 ~所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
; x/ S/ ~- \6 e, c# {( I& ?( R' b2 m
* Z: V  `! p, A9 g/ M' \- Y注意：是额外的内存空间，存储排序数据消耗的空间不计。
8 d1 _. y6 D" u3 i5 y
1.3 稳定性
8 P4 Y' P# b2 h( m' n
算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
5 }! }* l3 N8 u7 q
, l2 \- K) y- Z. U9 |2
* l! C4 v2 w# a
什么是插入排序？
7 g( u/ ~& p& w: d$ f- }2 t
( d  c: \: v& e$ S+ Z! h- y顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
3 W9 y/ o1 l) ]4 X) M# `2 q2 p
: w- m( D6 W- a( B6 Q
" w# h9 b& W) Y
9 l' I4 s, q& h$ ?( p  a+ A/ A3
1 b) K$ I; u% b' R' H+ ~8 }
如何实现插入排序？
) w2 \& Y2 T6 A' x8 E5 G
% o: a( q1 k5 h4 |: u; O2 I上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
1 H& }5 H# A# ?. Z. f% E


4 v4 b& Q5 n5 V! n& s首先我们要将数据划分为两个区间，已排序区间和未排序区间。
2 N* u  o1 P1 R/ _& S2 s# f1 s& A* u
: I' g2 D# r7 v3 k8 B

# ~. S: P) ?- p2 g, e

$ r" L; K$ q* Y2 d6 c我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
$ ]' ]$ H1 Q' F: Y9 E! G( Z1 `



  v+ {& T+ l3 [% B' z
  `3 }8 _% y9 F+ J如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。

. ^7 h4 M" ]$ \7 M# d5 h
7 C6 f  v( m! T7 g& H  w
  O  @: X, f+ j7 j

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

( r; h& p. j( f  ?4 G5 t" }( l

4
, H6 g2 f+ I8 g3 @2 V% {
插入排序的性能
" f5 \8 t" A# k7 w3 @" l4 ?
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。

4.1 插入排序的稳定性

再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
; O! A1 O7 }3 m  U9 ]
! x- b6 R$ B7 q+ H/ c; t" P( O/ ^2 P4.2 插入排序的空间消耗
7 K+ a9 g! y3 j' {
7 n3 Z2 B9 B" d我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。

4 q  m) d. s  T# E) M4.3 插入排序的时间效率
+ P  l1 O$ D4 x* ?+ U
. e* k( h9 H6 z7 s插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
( a3 P/ n( M4 t% m; \% C2 m& S
' I  k& \, v0 Z+ X& i如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
# E  t) w% f7 `" t2 U: i2 O
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

5

小结
4 K% I" x- q# A: }
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
, w2 n7 h1 v( n6 n: O
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
* f/ y* f. k. a* v9 I
/ v8 o) _* Q& M3 c* R% q7 J4 Z元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
7 D9 S. _7 c' o: A: b
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

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

对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
- m9 A- @: d0 j# s  Z版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: H" d6 `, n' k; b4 n. ]& j原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708

6 ?) Q% w8 }5 {4 s$ J