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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
& V7 W4 j) U: K. ^4 u( l) V
7 k! h$ t2 v% v1 `8 R& W2 S写在前边

4 c  D& l- p) L1 t  r( s
# h, d0 w1 S; F排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
, k8 }9 p& o* U) B5 z- i: s
- C. ^! h; {4 @5 Z! r虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
& J% ~* S. C' U7 R9 R! D% x
% E: l/ Z7 l) @7 l: D0 [' g- `那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
5 P$ W0 Y, D; l' Q  y% C( G  g
思维导图

* w& n6 J' y; h

" K8 s, @* _/ ]0 Z
1

如何分析一个排序算法？

% U9 [4 S$ X+ r1 T2 X3 R0 t( C之前写的一篇很详细的文章。

佩奇学编程 | 复杂度分析原来这么简单

* j* H% O1 j" R$ q0 R; J* b分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
5 ]( c; t: ?+ V. W0 B* n
1.1 时间效率

这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
' \4 s3 ^# z  L" {* x7 h- V
  ]6 ^$ W1 D: t7 E6 U复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
/ K7 N; ]1 A  e& G
/ E& H8 Z5 ~/ \2 s; v对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

1.2 空间消耗

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
. m4 }; R" J7 k8 s8 J2 ?
注意：是额外的内存空间，存储排序数据消耗的空间不计。
6 h6 m7 x7 e9 Z3 L" c5 |1 |
1.3 稳定性

: Q( R: F% O1 l2 M0 r: s& A5 w算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

2

什么是插入排序？
( ^6 ~& \4 ]8 Y0 x
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
# e1 T5 [/ x) k

1 z2 w* S2 w, H4 Q- @+ a
& p9 q" k" R; g" T7 D+ ~3

如何实现插入排序？

; r( ]: \# W; g( x上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
5 c: W7 e& R8 p( r" V7 o
' U  Z0 q! U: R* h
6 [6 l: s3 L3 |! N/ {$ g0 [- ]7 l
3 t8 K; u0 X# }. X. L首先我们要将数据划分为两个区间，已排序区间和未排序区间。
& m' w9 I/ r' w" Y; J3 q
) A, V9 S& H& Q! ~  @) K

3 Y, [* K7 X% B5 S
. z4 I( z+ G" @/ u$ H2 ?
6 j0 p2 s% A& d, k* {* o! C* ]+ x# u我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。

; F5 o/ k4 a4 [; \7 ^% K3 H
8 G! P4 R) H- s, B


如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
! Y; z8 a: ^/ b) b) g3 J

% Y9 X4 Y; a+ p0 k% I! V! E& Y3 `

( i/ q! w* j: k  \9 D0 ~% [
最后我们看一下总的插入排序动画和代码实现。
3 ^+ s8 k+ V. `- Y9 Q$ G8 ~1 _
1 s  r1 Z* M9 _0 }

4

插入排序的性能
: j$ T' i+ q7 @: r7 a: X
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
8 i2 A; M# [" T4 I
4.1 插入排序的稳定性

( S" C- v2 p& H0 S! w再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
4 Z2 k6 K6 Z. H$ n9 c
1 w* t$ R$ n8 C- {3 z4.2 插入排序的空间消耗
7 @% ]2 n& x# p. f- C8 ?9 L
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
% e2 `: k# f0 \9 q6 z. v
4.3 插入排序的时间效率
+ @2 x7 S' u* l3 p
. n8 r) V* ?2 d# L% s插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
. C4 k" M( t7 w* I
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。

5

小结

) w4 R4 X* f. D; P9 }# R/ A  A2 j我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

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

& u: i0 G7 Y9 R! |9 k' z元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
  W; t2 [3 {" x: v4 `) ?1 E% G* a
; F% p% d9 L- v7 F( _有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
& c1 k5 r0 G( i. i5 w  W& D
7 |5 |5 |7 B& \' J8 `虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
4 g! k: P1 E$ a2 E9 H
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
* e9 a3 b' U# r————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708

: e2 r1 T; i; o* `! B, u
" D7 F; N( U% {. ?9 k7 R