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

杨利霞

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

+ h: g; G4 n$ p. a  h/ v# F7 ]7 }! `写在前边


9 w/ ]1 `4 F. k  B+ l( V( b6 u排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
# G1 j  H" d7 U. f9 L4 I
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。

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

) f' Z8 G2 C4 u8 C0 K思维导图
# U' l4 L$ _) I' r0 T



1

0 T: s9 o$ s+ W- X" @如何分析一个排序算法？

9 S( P; r% {: C. ]( Y+ w4 m之前写的一篇很详细的文章。
$ }! j- t/ x4 X0 {1 c1 j0 k1 j. V
佩奇学编程 | 复杂度分析原来这么简单

分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
; J) X* d2 \7 v; j- S% L
1.1 时间效率
9 y1 P. B7 y; k+ n0 E/ @! G- c3 N
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

' D+ z: _. r) Z) J9 ?1 p* h复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
4 J: p% k& c$ `( A7 _* R
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
# e$ m# s! `- }. J
1.2 空间消耗

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
9 U, b% c( Z; N" Y
, c4 x  f2 e" D5 ]2 d  l- q注意：是额外的内存空间，存储排序数据消耗的空间不计。
; a+ z+ M& K* |( ~& d0 F& ]* z
$ E" w1 ^8 {- e9 t1.3 稳定性
- q! k& m" x$ r( e& W" w+ `
7 c+ h# |0 o" P0 \. V算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

2

" v# j& G& \  J7 v) c! r  N什么是插入排序？

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

% c$ b/ h' I/ S/ M( t

+ y6 }( l% K* R* l' \& W- {3
  S: X2 }6 O& B6 K, s/ G
6 H7 E1 k% m7 R* ]; t) E# R' u# }如何实现插入排序？

- [# c; T6 ^7 V5 f' ~* H" `上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？

: C& D1 _; l4 `5 E' g* u# Q6 v
! W9 p* P! {& s4 d& J# Q# b: Y! N
首先我们要将数据划分为两个区间，已排序区间和未排序区间。

! A7 a, `! d0 x: g# a- ?
- Q  ~5 Q2 E% S& e5 w

5 ]. E9 j% D( C
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
- }5 J+ t4 ]! m! L6 j- W
& l: f1 o1 z1 R4 O' Q, W& X0 Y& f

, [% Q/ A4 s4 L8 o3 K5 X  |

. B  J3 _% j4 w; R2 o  j  c/ Y如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。



5 A4 D9 V* m$ C4 t" w1 Q8 e

最后我们看一下总的插入排序动画和代码实现。
  K5 k8 e9 M' X+ O0 V9 Q5 u7 V( v

6 g! V: D, x5 w: g% [; C5 k0 U# Z
) O2 C  g$ ^6 H" ?3 N. t4

# V* n6 V. y- h6 D, y) }5 |+ A8 w插入排序的性能

5 ^! s" Q/ ]" q" q, G/ K6 D/ X我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
$ t- |1 h' N' C  w" ?, w
4.1 插入排序的稳定性

再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
/ o0 X7 q8 l' c  s7 ]+ B2 \6 S
4.2 插入排序的空间消耗
5 z% _2 ]8 n7 W& A( ]! E% o# t: Q
3 q; N$ `- a1 S我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。

6 m! E. X5 H2 N9 b4 \4 B4.3 插入排序的时间效率

7 W2 n3 f, U1 {6 W/ `4 Y* r插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。

8 I; l7 u) K2 N  I5 D如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
( @! G& {4 ?0 ~3 M
  ^+ i+ ^' l3 ~1 G* f( B4 K% }对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

5

小结

我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

1 e: c& A  `  g( G3 u) I我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
) _( |4 ^% S9 _
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
3 l  B: K2 e+ B) P( e3 L0 N
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

* B( f# T  b6 f5 T! ?- p5 ~对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
- F: o1 c, k7 p" w' G————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" j. r* n7 A& W原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708

! Z) C: a7 m* e  Y& R$ o  s
0 m- J& Z! [3 z! L  ]3 l8 B( c; t8 P