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

杨利霞

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

写在前边
- M& e* e& m1 s! t: {7 C
2 {# }" ^# c6 K, E2 R* c
$ S; X1 r. H" ?2 x7 ^/ \1 k排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
& b& i. p4 [! M; y- Y# }2 \
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
: l; A# y+ X2 s9 F5 g9 R
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
2 M( I( f  w' C, v
思维导图
1 L/ U8 ~9 U. n: O" _+ k. @
) Z* `! o6 n  B* ~
* W& @  M# c& @% k/ a: g; Q% s
  i& F- u9 G: C9 Z' g- g' T
  ~) z0 e, Q5 K2 \  ~) N" I1
& {9 I, i8 @# \# o. e* c( r
如何分析一个排序算法？
1 Q9 S; t1 T2 B$ X
: u& D+ T( m9 A# D3 y$ m之前写的一篇很详细的文章。
/ H, J3 C/ Q; r, ^  ?' _
佩奇学编程 | 复杂度分析原来这么简单

分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
8 k" g' Y3 V4 L; N, N4 {
- a- g' P( E+ f; t4 F, F7 z6 r1.1 时间效率
/ X9 f# b7 w3 p4 n9 Q+ k$ {  J) B4 R
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

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

3 ~2 Y3 Y3 }8 O, ]对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
, [$ w' I: q+ i# |
- L/ [" c% P& _5 [6 F4 E1.2 空间消耗
2 i* M4 y# x# w! H+ E
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
  E' V7 b* H6 q7 {
3 F2 J/ E  I1 j* S注意：是额外的内存空间，存储排序数据消耗的空间不计。

1.3 稳定性

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

2

什么是插入排序？

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

1 _5 c  |# e9 V! C$ \* X; E; T

3
$ e) k% q; p; v) R# S
& c' J7 f* B/ ~7 D! W+ y如何实现插入排序？
4 i5 Y/ X/ h& u: X: m1 `' p& y
& a0 L1 J5 {( }% v! A上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？



  @5 X" x4 ^6 r首先我们要将数据划分为两个区间，已排序区间和未排序区间。
0 C1 G0 K0 f# ^

7 h! H1 i& K) ~2 j2 T3 o6 a, F
: W: N: F  s3 Q* l/ [+ M
4 O( i5 w8 r' e5 z$ Z$ x/ |3 O
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。


4 Y" e; }7 T8 J' C8 M
2 {: n/ N2 [9 u) D2 y+ e

如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
. I& H+ D' X1 i4 ~
2 h& ^1 N5 o/ _4 w1 j- `
3 r7 k4 f3 @+ L' r/ K: }9 T; ]0 t  m
  {" C- T. U3 L5 E
1 v$ M4 T5 i0 E8 k! z* C
最后我们看一下总的插入排序动画和代码实现。



4
3 r! A5 k& m6 t4 @# z7 S! r: [
插入排序的性能

( K  x! u% M% x0 G- S我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
! X+ l" C. l1 w2 Z! M; ~% F2 M- p, U
# }0 W) N4 f! K( U, X) _4.1 插入排序的稳定性

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

: ~6 B/ l9 W1 k% C  ]- G, L4.2 插入排序的空间消耗

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

/ ~. a- O: H, K4.3 插入排序的时间效率

6 H2 d, d( G9 ]$ h( H! R插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
# C6 ?  X6 N/ L6 E. h# E: E
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
. @7 A! S0 k0 C- m: g( y( C* y
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

5

小结
! I0 w' B/ C  b$ V' @) S6 K0 Z
* |. F0 D* z1 ?- B+ v3 m我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
7 ^: m, Z% A; S
+ G, G" W! m& }1 r7 x我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
; h4 M  a6 j" |% p
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
5 q* @: P/ d5 U/ X
4 s& j" L7 N6 J, V有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

$ j6 `6 M. m6 q( ?4 Y7 X虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
1 q" W2 ]4 J6 S1 q7 f8 Y0 I6 X
, G2 ?$ n- T7 m+ g( [0 B" Y: d对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
- t* J& O8 O7 |版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
2 T# b% r# k. E& S