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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
; i% W- o0 W" ?
& I4 j$ U4 Z5 F, b/ L写在前边
8 a! w$ a. M0 z# m9 R
; A2 @+ o% B7 _2 H" S
) U2 f0 ?1 W& t) F) ^排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

8 V6 u" b# C. s% F# D! B虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。

3 C% X/ c# f! k那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
+ u/ r% m# u4 V2 E5 m
思维导图


4 O2 ?' y2 ?+ o, _% @

1

如何分析一个排序算法？

之前写的一篇很详细的文章。
% D- \( u. Y1 H7 Z4 e, t) s$ x6 h
/ J) J- {( O; K+ ]6 S佩奇学编程 | 复杂度分析原来这么简单
  ^) Y! y# j9 y/ ^! k
$ H$ z% ~+ B) C. v; P分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

1.1 时间效率
1 l; r" m$ l# I5 M8 }0 O1 k5 C3 D
9 Q5 k/ u6 x3 {2 |5 f  m5 v( b9 F这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
% z4 c- G1 h; i' e, ?+ O5 [. W' Q
  ~1 q. u( F# E! d0 T  M: h  X对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
; M8 v$ o2 u! P1 x4 P- l) y
1.2 空间消耗
: h+ d$ m/ z% i  T2 n% m0 w) N
% f+ F/ j5 v( p- S* h. e; y所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。

* k: D% ]- p* n8 m( x注意：是额外的内存空间，存储排序数据消耗的空间不计。

1 T- }+ y6 e4 t3 k" ?, ?& K1.3 稳定性

+ e: g6 z+ C& E6 m  ^. m* I算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
2 e# K( w/ i) o
/ `" B* R' a# w( F4 q8 h2
5 r7 E6 t* h. G8 P2 j$ O
+ c, ?+ ^3 b4 `* y什么是插入排序？
/ Z; n- w2 U5 S( L
) _! J! h& m$ V4 a: q$ O& S( i6 i顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
! L% }, w  }* j


. x. v& K, }. |, }( D* x; U; ]3
" M1 F$ e" U( p+ f" V- n
. @/ t& W: D# B0 B# Q  [如何实现插入排序？
8 V4 C  j7 {/ g. ~
! z6 \% N- {; y8 `* G  j0 {0 n' y上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？


' w7 @1 @5 b  k8 U2 C
6 I9 s; f3 G  m8 I# f首先我们要将数据划分为两个区间，已排序区间和未排序区间。
: ~, P) _. M8 E" F9 q4 V. P
  A+ H* d6 ]% j
* E7 t, r6 z8 I  I( ~9 v
" y7 f8 N' S, d' E

4 u4 G  h1 @' O+ R2 b0 l我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
& k' U: U' _  P& g3 Z, B
+ L  ]# v9 p# ^" W
9 }# [6 M# P$ O9 C+ w0 c$ J

5 {* K1 O# a4 [% B" ]4 E5 ^! |  T9 C
% L7 i; ]7 O) M6 }+ w8 Y6 @如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。


4 h" o; c' `* D

" P% ]: e7 L+ }; Z; q+ q+ }3 n4 j
, P8 I" i* s- p8 y1 b. b( t4 I最后我们看一下总的插入排序动画和代码实现。

$ Z6 G9 @- ~% I! l

, t% m. d7 Q& a5 o4 P4 [3 C4
3 E" F9 h( p8 ]! B9 u
' d8 I/ F8 }9 M" }; k插入排序的性能
+ ~, ~8 k" k; A9 f* U
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
; ~2 N8 Q- g5 t. y
* d3 Q3 w5 l0 t: m  D7 |" f! D$ v4.1 插入排序的稳定性

再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
4 F+ t" Q, X! c# X, {8 m8 L
4.2 插入排序的空间消耗
' y0 P  W8 b: B# U* q
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。

; P0 `  ^# Y) f+ Q+ Z: i4.3 插入排序的时间效率
/ F! c( e9 R" E: m0 I, Q1 d
- |' m$ M5 ]9 F3 g插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
7 K+ G2 A$ I8 \# j! Z- e! \( I
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
8 e' H3 q" A1 O/ b, p: l8 F
! y! D4 u5 S: ?( @" h对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

5

小结
7 D/ y- |+ e8 Y5 o3 i0 o
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
2 X) U: y- J+ q* t/ D! B, ?
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。

元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
5 g$ O4 ^+ H2 h/ C
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
; ]7 @- g+ A6 C  h
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
$ \% M( ?/ {+ P! k4 R( Z————————————————
8 W/ ?+ B; C) y版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
. O& l+ Q7 Q7 V2 e5 C