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

杨利霞

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

写在前边

9 c: C% j7 h9 q8 {3 W
* ]) o; F( d: s, t; \; Z排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
; m4 j1 ?: ~6 {$ U5 P
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。

那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
8 x# n: E; F0 I& v' E1 c' O
思维导图


; T1 m$ P2 V) q
' T! p. C5 S7 M( K* M( [; N
$ ^% o3 v5 O# @+ T2 B1

如何分析一个排序算法？
+ M0 k/ X0 ?5 E$ I* b
之前写的一篇很详细的文章。
9 }+ b; K, q& {: v. u: k3 c
佩奇学编程 | 复杂度分析原来这么简单

9 c7 J8 y' l! k6 b# A* _# S3 [+ Z分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
( c: l6 A5 ?& l2 Z
1.1 时间效率

# A0 M9 S( P  u: ?& z5 U% U, |这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
) h# o5 g' K& A. _5 f
复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

+ O% z3 L: e/ `. X; g+ m% B" q3 T对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
& Q- H0 V8 z8 Z5 a8 N
- i$ _4 \: m- O1 G2 [1.2 空间消耗

# N/ v8 g+ L, b( h所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
# @' H, X/ |( S- N+ m% Z/ a
注意：是额外的内存空间，存储排序数据消耗的空间不计。

  p8 d0 }" G& I1 P7 G  C/ k1.3 稳定性

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

2
! P7 x/ W6 a* S# G) ]5 G
# y( b0 E8 h* M  D( b什么是插入排序？
: O( l) ?1 d0 `! l$ K
/ X3 h+ N" f6 O- }3 H( R1 E& C顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
5 s% j6 G7 P; J2 I' \

- H7 S( _3 U- F5 x& z0 g
3

% z# {6 m7 n$ f2 k3 G; T如何实现插入排序？

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

, c, A; |/ a& B! q: M, u

) z! V0 j- c( u) _0 G首先我们要将数据划分为两个区间，已排序区间和未排序区间。
) d! g3 h1 z# A" h! S7 @2 f


, {5 C# Q, c  J2 ?4 w

我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
: Z* V1 w# s0 X4 M; K( f7 I1 G
3 F' y6 R" g1 k6 A5 S$ V4 Z
* o7 X3 D& g( y" T. y
) e0 p  }6 z  f6 A' j
% a% z6 M- T9 ?
2 ]7 k' F. K/ B0 q& G  Z  y如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
! i  k6 z3 B2 I* S



; j" i3 O$ b7 W, x  |1 ^, v
最后我们看一下总的插入排序动画和代码实现。

7 r- o) ]# `6 _0 v8 M- O
9 }" S* [; E' F% _
' A: i7 v8 Y1 `4

- `, {9 L( i9 i9 U* i( Q" [  h" w插入排序的性能
4 _8 n$ F& S- U  {- {
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
: g" A/ b5 y& O8 c0 l7 \/ Y
5 V' n( s6 `, S; h! t# M4.1 插入排序的稳定性
9 l) l2 T. E- @! I! s6 x0 B" y
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

5 a) t& g: e( Y4 o1 F4.2 插入排序的空间消耗

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

5 g: A. i2 P9 x- z4.3 插入排序的时间效率

插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
3 h0 b$ U/ K5 ^) g/ [. ~! ^3 G
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

% ^- `- s: E! [对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
3 q; _+ q* m% R9 |' ?
" E  I, I3 h7 T1 i1 b2 t! L5

小结

2 S# F5 P8 I% E) G8 F2 e我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

) x5 }+ [9 @' ?: E我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
* P3 U$ z: H' Q
7 [6 K# H% Q/ b# W  ]$ T- S$ H元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
3 e0 x8 ?2 [" F/ t6 F# a9 x! s
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
6 D4 r) N5 s: H+ V2 k. _1 x$ f
: K9 s4 j0 S1 @* v; X, m对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
) Z6 K) d2 R7 h版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
1 O% g  [9 s2 H0 E- F