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

杨利霞

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

写在前边
8 F4 t! G* ?) d- F

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

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

5 I( c7 L. @! I9 L8 g那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？

& Y! B7 |& J& V1 o/ x5 g思维导图

# z  [/ B7 O2 B" B, ?
) P  }9 m! f6 Q( |/ p! L

1

5 z2 A$ r  ?7 k3 n5 j如何分析一个排序算法？

之前写的一篇很详细的文章。

佩奇学编程 | 复杂度分析原来这么简单
, h/ Q1 q* ]1 ~: D
分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
) q* q5 f/ S$ [' a3 K
4 L, t# ]. k/ F$ Z, F. u3 x; g1.1 时间效率
' U% S  N8 I  b% A5 t7 p
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
% O  D6 B$ C2 _/ |
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

6 k% x" T& w4 R) s: Z' l6 `6 Q1.2 空间消耗

1 w7 a% p$ A& P! f8 @所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
/ g5 g8 ]: ^( s& [, s3 C
1 D2 r2 }+ W2 }2 g# S# u注意：是额外的内存空间，存储排序数据消耗的空间不计。
( u; z% }0 n9 @# @# d5 u6 L" S; _  E
1.3 稳定性

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

什么是插入排序？
  `) b7 k) m$ B+ d6 X7 E( n
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。

+ N. E) w1 `  P1 n/ G: z

8 g7 A4 c- H# ~4 H& F3

如何实现插入排序？
: L' `+ }7 [) r4 m3 P+ p
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？

4 V- ]+ |- W4 q* ^* X- @6 b0 C
( G- K) m: s) V
首先我们要将数据划分为两个区间，已排序区间和未排序区间。

, h  o+ Y  |* `/ Q. t4 D
" ~! d& q3 e1 N+ M


1 a4 l, u& \% a- g我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。


0 ]% `/ y/ B; z- J8 `4 {" T; I
, `+ c! f8 \$ b7 E/ f& @

如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
" K4 H, c7 l! M3 d

9 }& }" c5 E, h5 M2 C$ `: b0 j
7 M7 ^5 ^4 h4 q. F6 B

& T0 X" K1 Q. ~" f最后我们看一下总的插入排序动画和代码实现。
4 h# s1 A6 @# d$ ^& f. c# g6 y5 D. g
3 {3 Q9 r$ K4 E* v7 |
* i+ H1 ]3 s5 k& d0 x
) C0 j. n; y% z" O6 M0 G4
1 d0 R. r: S4 W: }) o5 U7 g
. ]) e. G; c" Q) r& M6 ~1 Z9 Q  c' W插入排序的性能
/ c$ N+ d+ h8 W' N$ v3 f- Q& t
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
1 K1 r0 M5 b2 `" Y' z9 B# F6 @1 t
4.1 插入排序的稳定性
& J4 A" [6 g& f2 }
& C- w, G# T" O1 I9 B! R; t7 Y再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
/ b  ~- Q) l( q
# x0 |8 c& W4 z$ n# b6 O: o/ T4.2 插入排序的空间消耗

我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
. S" k7 m4 M+ u& j' |( G
/ f5 u% X2 a0 E+ y' l- w( s4.3 插入排序的时间效率
% b3 u4 r* V  G* f& x( K3 t
插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
9 G/ B  d+ D% n; i
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
  j5 S+ W& G: ~
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

' J, A  b1 k; q9 L0 k5 n7 q5
4 w0 ]: R. @. y" r, l
小结

我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
' V7 ]4 |/ Q1 p1 A- Y. D) K: A5 m. n
$ w. @/ A9 n: n0 Q我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
+ L$ ~" I6 I" H
- \) c1 e: M3 d- Y元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

' R  l8 Q; \( Z6 i9 D有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
7 K+ O  g# M2 O1 V+ ~) |" f
# N; U2 R3 y; X7 i, Q& q$ g虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
. A/ a& W4 K; q% C: y) ~: N
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
3 ~/ W4 h/ ^0 f0 r+ w————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
/ g5 b$ L+ C  ~# h8 T原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708

% W% y* X) J( l' ^