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

杨利霞

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

写在前边

0 F2 j7 _1 `, x2 J
& r! a  D# d2 O. b" t" K7 E排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

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

那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
' \! v* @2 \5 Y$ U& f! n  O
思维导图


8 ?, A3 ~  D. e" ~0 E

1
' |% D9 C! W" Y4 [# P9 y* Y
如何分析一个排序算法？

0 W; f' q& e' o; Y) ?+ M/ @% X之前写的一篇很详细的文章。
0 k( Y5 M/ y. v7 j# \
佩奇学编程 | 复杂度分析原来这么简单
' p1 p; Y; ?  n# }% H
' f, V9 q5 V' ]0 Q7 r分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
$ }# X; c1 W& j4 s8 o7 A
1.1 时间效率
; ]+ a0 c3 r. Q: W/ M
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
" B. f" L; w( G, k1 Q( n
  b+ l5 |5 U5 f4 b% V7 k复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

, A' k4 Y1 i8 w8 _) _对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
% J5 c, D5 X$ d( O+ @4 p
1.2 空间消耗

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。

注意：是额外的内存空间，存储排序数据消耗的空间不计。
5 a& B! X- ]- |$ Q/ u
& l. `! Q7 j: U6 I0 w. {$ q1.3 稳定性
. J& w. ~3 n" @' }9 v: A
# s0 X( {8 h; V: s! [+ H; W算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

8 M5 q% j% {$ p; h( u3 n5 \. ]3 b# @2

: P8 t/ M5 O8 M什么是插入排序？

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

$ m* N/ N: Z* u  R" j" n( a
4 Y$ ^4 {; J1 H" n# i7 g. Z+ A8 |) f
! g! q' s$ N( {8 k( a3

9 ?2 @: t, q# `( G/ D5 A$ R/ @, D如何实现插入排序？
3 ^. N9 k  f* c2 x; u! e) ~# X
% v7 h4 N$ a9 ^9 u: _上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
7 b- Z- s( L& P8 v" l0 P

$ I, i/ a3 \1 t6 Q
4 a( D" d+ k. i0 [( u: g# w2 q首先我们要将数据划分为两个区间，已排序区间和未排序区间。




. `/ u$ H" B& a1 |
2 e9 ?9 v. U( i0 E5 T我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。

  |6 u, P4 W, v5 P* @
6 D. V8 u3 C" g7 J/ D$ \9 Q2 z


4 N0 O5 k% z: U6 l如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。

7 N* S9 A- @1 m0 d$ w



最后我们看一下总的插入排序动画和代码实现。
* x9 t3 x' F/ d; ]' J9 _
( m# H# V8 o' z5 w0 ~# }2 G3 ^

4
- \" p) [" L2 U  N, ]
6 G" R* g& ~8 S/ K+ g( N插入排序的性能

6 T% |$ t& _( H: \  t; \- @. v2 d我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
0 t& W  s1 J! O
1 H3 O5 Q: O( i- E' p4.1 插入排序的稳定性
% ^/ ]( D( Q  w' K& J
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
& |7 k3 w5 H4 S  O1 X
9 {+ |. k  L0 ^2 l; j" A* V; L+ x1 L4.2 插入排序的空间消耗

/ f4 B$ R' y. V1 _我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
' _, i7 {' a$ A' I
4.3 插入排序的时间效率

/ f% R4 W' G8 @# m8 l8 |. s插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
% n* ?! Q5 H0 t9 @
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
# o* [* |0 t$ i) u
# a2 p  f) B+ q对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

% X+ u4 i4 o/ I  b, ]0 o: R* A5
, D! P) V/ P2 O. {( M5 n' q
小结

" h8 A6 ^7 V. q我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
+ K; Z; f+ G5 c& }$ {8 A' ]; Z: j" L
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
" O8 t+ n9 z1 U0 B5 W
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
3 Z& h/ ?; j7 b8 y  c2 @2 Q1 I
4 F# M% [! x  S  L; E2 }虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

) I  l3 s! l3 P- x8 b- o对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
; `. v% R: b# b3 S0 {————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
. e: T  R6 O$ D1 m6 P, v+ j
0 d1 H- _9 s9 ?0 s$ ^! a
2 A; U4 H) T, ]$ M