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

杨利霞

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

6 E% n& K- B. z& h! \+ |4 y6 Y写在前边

2 ]# o" M! H" p; l; K1 X
$ w. a) v0 u. T5 S  w3 K# l5 g排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
4 k1 \6 P9 s2 O
$ c$ h+ k. {: Q4 ?) U$ m& W5 {虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。

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

3 P5 E6 z" d( p+ @思维导图

2 S, P) G1 a+ L7 o( K7 z( X. ]; x
( _* Q; m' E% C8 s  U( O3 j% T+ y4 K
  R6 z1 A' J6 B! A
1
" ~. h2 Q2 I+ R4 E) Z( Q
如何分析一个排序算法？
9 Y- s, \7 D# _$ g8 J
之前写的一篇很详细的文章。

2 I9 G! q8 Y: I; R& {4 M5 j% p: p1 S佩奇学编程 | 复杂度分析原来这么简单
! y" }2 r. M, L4 s: ]2 U* F
+ z+ \( e- }3 R3 u. W9 I0 B- h* |分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
# b; W: c5 b0 R: C4 l! }, w
1.1 时间效率
% x1 p0 N/ [6 M) g; A- H
/ @9 ]4 A( q9 w这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
3 i& z. }; C- R6 }! n" u* }' y2 A9 u
! r. @1 A+ ]2 q$ E' a6 q复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
& o" h% \# L1 \+ W- [
- u* q; q! T, k3 T2 C1.2 空间消耗
" k0 n1 _3 ]8 N- d* R/ ]+ j& o8 H
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。

6 a; e/ @, Q* t注意：是额外的内存空间，存储排序数据消耗的空间不计。
- Z1 ~& \. D1 j( R. S
1.3 稳定性
/ R3 o) i( G0 \0 W  N; H
: ~- ~' S) R% h3 k0 C9 |  g算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

2

& @3 y* I0 R, t2 g4 K什么是插入排序？

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

- a0 r6 Z. j* i: B

3
% v0 G  W& S7 |, v) b
如何实现插入排序？
; A; h, q7 P5 L/ }# P' Z
1 v0 s+ p. |" u5 K- P% j上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
2 {- D- ~/ _6 ]! Y# j  Z- n

& v; Y! b& d" [0 o7 B+ q  x- D1 h/ O
- B6 o( [, S5 c首先我们要将数据划分为两个区间，已排序区间和未排序区间。
, x" b' _- J% r, d- d, F, X$ Q6 [3 n
6 I) i1 _: t% X9 W: {



- C' ^. g' @( d+ }我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。

( ]- K& i/ k$ `; d, c, G2 T+ h/ k5 \



/ E% L4 f+ Y0 `. ^5 R0 b+ H" `如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
1 L' U: @1 W( H; g
  _. l1 S' z2 p$ `  R+ h4 c
9 ]: z# L# R3 i4 b5 V
, _" Q: x- c9 I1 g$ P9 l5 q

/ c: r+ n6 O3 z* v& N6 B最后我们看一下总的插入排序动画和代码实现。
6 {: p/ C7 ^" e; Z" u
) P4 v0 J0 y5 V' Y0 X

- Z- ?# {9 f" k8 z5 t0 d4

; ^2 N2 M! t: p' v: l插入排序的性能
# ?. Z4 Y9 J3 f2 b
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
. t7 J4 \+ n6 t6 q
( s( [7 F- h/ c0 n9 Q. F4.1 插入排序的稳定性
/ v+ R2 r2 ~8 l3 G" `
: T& o" i9 U$ F6 g1 p8 B1 h! M$ a再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

4.2 插入排序的空间消耗

' j" B5 T9 z: T我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
- |( }6 A7 V) h6 S/ Y" M
4.3 插入排序的时间效率

插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
  U; n! w& j# c  q$ u( z# R
+ t+ D5 ?2 v, q# E& `# V1 p: D如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
* G/ S. K- @8 c2 q; r
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
" g0 X# U* i6 l9 D' s; i1 {
( B0 M$ p& u& C  K! t& t; g! E* G5
; l  W. R, u% n$ h+ _! d
小结

7 K" [, J. D3 H* K% B我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。

7 i6 c$ c$ m7 `" E3 ]2 q' M; n# B元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
1 K/ n. B" N8 S9 e8 l
& ~/ f4 a+ \) s  s有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

: X/ d; k$ h3 S7 R: Q0 Z虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

6 q2 N3 t9 n) B7 @1 Q对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
! h5 _) X* x. P) @7 a! X! v% G

) ~  Y( o. M* w: D1 C