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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
/ G+ Y8 D- p" V! n8 R
写在前边
3 z1 K' n! m& y3 a; ~
  S# S, v/ _2 F& F# k! C! ^
; _; B$ b/ ?& b排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
; {" Y5 ?1 P6 X; ?6 k+ ?' F( ?* p' \
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
" y( q0 m  D7 }; c+ \
思维导图

4 d. A: Q: O! o2 q* Z0 b

/ k# c& P3 l, f& c: L7 j: r2 C
" {0 R% Y# E5 g/ X6 l3 ~% c1

如何分析一个排序算法？
& m7 i! _8 r/ U7 g- m
之前写的一篇很详细的文章。
+ _2 l) F4 ^/ k
# o2 Y5 y, A3 }4 O$ v佩奇学编程 | 复杂度分析原来这么简单

* F# U6 F, Q3 J! m) W! i分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
% z& D9 P* a5 t' Q
1.1 时间效率
: @/ {, n6 a- z7 I. ~/ F
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
% J8 c/ f: n7 J$ r+ Q
, H/ M" i7 N* {$ K/ D: X$ j复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
. v+ v4 h5 f% f1 L3 _
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
% H& p  @7 x1 q  }0 N  C8 S4 v
1 ^6 E+ y9 ~0 K1 U8 v! d, k' z2 P1.2 空间消耗

) b7 i1 L  x" V* }, H- |所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
4 W; N7 [: l: r+ Z" m1 `
. H& k& D2 O# o- J! y' ?/ R注意：是额外的内存空间，存储排序数据消耗的空间不计。
+ S6 T# j* T9 |" y0 _. G
- M6 m" O  i5 t1.3 稳定性

) B! q# E, B# @5 [( e. T' j算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

) ]! a. I7 o+ c( k2

什么是插入排序？

" a3 ^5 o' ^) O, T, I; [+ ?顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
' A0 k  ?2 [$ ?1 h


3

& _) ]2 V: L3 f9 @, G5 P7 L如何实现插入排序？
! t8 y- u4 i, L/ x% M0 j  @
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
; |7 B- s& S9 p

( W9 c( P+ b: y- e
首先我们要将数据划分为两个区间，已排序区间和未排序区间。
( U: N; H: D3 \% d) u9 c


5 Y1 V& _+ A* f" ~% y9 Q
: m7 \4 `) U% @9 I# h! t( `" J
/ t9 w3 m4 ]" J# Q( W我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。





6 K( ]$ H1 N5 v5 C% Y0 C+ @+ Z如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。




, k* s6 d1 D* ^; ?# ^! D, C
最后我们看一下总的插入排序动画和代码实现。
0 j3 u& C. E6 r) @( g+ ~6 q# ^: y
2 |3 n- n2 V4 [) p+ N9 O
  \4 y: {' E" _/ r8 t% q
4

插入排序的性能

我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
8 r- q, X& G3 q6 ~2 h
6 R) a8 E0 [5 o9 V1 @+ y, s4.1 插入排序的稳定性

再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

4.2 插入排序的空间消耗
* f! y! j& b# E0 J
" q7 Q* ]( S/ {( i我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
: N( F! Q* u) k
- Y. _+ u. G. c- Z3 V; N9 G4.3 插入排序的时间效率
$ T/ @) [( n8 `2 P! T8 H0 s
  B7 o6 `3 z  B, x6 p; d" ]插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
2 V: A. J) `, S9 v6 j$ x$ Z
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

$ i( B* }6 G# ^2 r: N对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
0 x5 @1 E2 J- k/ e
7 A' v# G7 [9 z5

" E: u, l/ g8 u" X( T小结
% \$ X7 [& T4 l
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
/ \; q9 b7 ?4 J$ a2 M
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
* s, ^" W* ~  Z; p8 P* ?: j1 t( p
0 D- _# J  M2 J6 t6 M有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
' P. x1 ~' h4 C7 @
" p' ?3 N7 L& P* h虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
% F6 Y) h+ t# o( k& C
, \9 L( {  e& }& M对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
4 }, v! \0 m/ _版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
8 _, b; ]! a7 S- t) Z原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
. g% h8 z3 q0 [
) b# k0 W* A% F' `: q5 K# {