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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
! a2 ]4 [, ^+ s# M/ ^
写在前边


2 ]; s' l+ u* Z/ j: q3 \& G排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

  L7 X; U, J9 X. L6 z# E& h虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。

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

' e. b! n! K. `* i+ _4 s思维导图
6 i) A, G# H( M! W* A! s; `+ N5 w+ d

' C6 w1 ~5 I% Z

1

3 n& t1 M* d( F4 h+ e5 y  ^" d$ v! r/ \如何分析一个排序算法？

之前写的一篇很详细的文章。
7 L) \. E- t5 Y8 c" d9 D
+ q/ o& C4 C9 }' R( m佩奇学编程 | 复杂度分析原来这么简单

分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

* z2 M: [. |; U( _$ N, m1 [# j9 i. U1.1 时间效率
) A: o# f7 J; R  F& z/ e% s* |6 x. k
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
1 Q' A/ Q+ v! G0 ]+ t9 Q
4 j; P0 k! K7 g7 H复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

7 ^! `4 u2 z$ L对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

2 o9 [% U1 j5 H! Z4 z$ |1 t1.2 空间消耗

: h* k: u+ I" m5 i# E4 ?所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
+ K; ~; z& i+ L4 c' e
" D* L( ^0 a, Z  K注意：是额外的内存空间，存储排序数据消耗的空间不计。
- l- T! V# f( }8 x3 q/ G
1.3 稳定性

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

2

什么是插入排序？
: Z% x' b; S  t7 c4 y' ]+ L6 T3 A" R
0 \6 t8 K) e2 h9 l8 Y顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
% G" U0 ^4 q9 a! w0 P8 ?

( Q, B) F: y9 }9 i; v
# o2 V' t/ z% T8 o& \5 e8 W2 o3
( e* i; x% K- A
如何实现插入排序？

& j* O( H" e6 }上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？

# m7 l& I  e/ y! ]% L* @
. ^' H: l- x* f' K: ?# ^
首先我们要将数据划分为两个区间，已排序区间和未排序区间。

# l1 |! |0 f* A: U3 a
- t$ g* s4 k0 a! i# {) D( k! C
1 Y9 _" c& h. m: n) l, H$ T; b+ h

5 b! w, _% S; |0 w* m; g( a我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
3 m; i$ l- {# T, s1 L
. v4 x2 U7 L1 `+ @, I3 ?6 @! o  I' J
; E" k2 U0 x" c1 \
) E% y# j! }8 e8 l( u8 \: K
4 E# E1 u1 \; Y6 v2 n$ a; f' i
9 @  H, {; ~2 C& w3 g' W如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。

+ r# k' z! S/ L& A% I$ V. n


6 ?; L6 Q& N# P. D9 w
  c& p- q% o1 Z, u# }, M/ a3 U3 X/ @最后我们看一下总的插入排序动画和代码实现。
) ?: |: Q# a$ G0 o
4 `  U, i, M- R; {3 J( w
0 N0 C; L. L9 ]/ h( M* g6 g0 u6 H: Z# l
2 A4 P1 n5 D4 r) h5 N( b4
/ x1 g& j# ^. I% f: G! d
插入排序的性能

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

4.1 插入排序的稳定性
# J- i$ r6 ?6 R* o  V& h
& i6 O6 e( z. ~) T" `  v$ S" e再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
5 a( w8 Z0 p$ f6 q
  ]# O) u: B% p8 n6 W" E4.2 插入排序的空间消耗
' ]4 v& {/ C  d% a! n) T
+ w  z6 Q$ G# ?% C: j我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
& {3 u5 N3 g' E- y9 X
4.3 插入排序的时间效率

. @/ h) O8 V) J3 ?& ^$ K" K插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。

如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

" `/ ~* l1 z6 e! p: e  K: }' T+ s2 |+ G对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
# a% h2 o  O! g9 Q1 t5 a6 Z/ I5 S, I
5
& m0 C) Y# j6 o- E
9 t4 o1 i+ W7 N小结
# o$ @7 S# X; B& a4 j$ I
- ~  Y$ Z. B; S& h  p我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
- F; H5 |9 b" E5 g* S! I: W6 D
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
5 `% V! ?5 g) P& v
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
; B$ G2 @9 u# f  m- }
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708