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

杨利霞

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

写在前边


排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
3 w7 l7 K* e5 |/ E* r
% R0 Z. U5 w0 P虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
2 s8 l% U+ y' U& @, r
' k6 n/ f! T1 `; ]* k' N. H那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？

思维导图

" G- S" T- o( l8 P


1
3 A' r' }1 |# S: i4 R( ^; R( s# N
) V- J& {' N; H# K, |: c如何分析一个排序算法？
* x/ h6 q1 _* a! y& F! U9 A
: m/ d7 U9 p$ {之前写的一篇很详细的文章。
( j# h0 w4 X- P9 l- Y
$ v0 r0 [4 B4 j2 J' ~: ^( u佩奇学编程 | 复杂度分析原来这么简单

8 C9 z: v! D  k0 O! u# t" q分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

9 @, h6 R7 N7 K3 B9 _6 B1.1 时间效率
* m9 G' l- S$ ^% H- B
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
  H, s( n9 v* t
1 `1 u" G- G( Z: j2 j复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

) o. N( L) U, x7 t7 O2 e) t对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
6 n7 P1 P' H; b( K$ s8 d0 F$ p
. M) ?/ D7 O) _# q# y/ @  b7 I1.2 空间消耗
8 ^' |; l5 P5 G( i
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
/ T2 l3 i$ {# M7 M: |
. ~' v2 u& _$ L7 C注意：是额外的内存空间，存储排序数据消耗的空间不计。
  d) B% ^! e( s1 F: j0 }
' e! K0 ~! M7 G) D' Y" U; c' _1.3 稳定性
5 M0 c, u4 s' R9 n+ ~( J
: W- c% b0 t- F. ~& y8 b& _: ~4 D( t算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
9 Q8 @  b- t, H# T: K
( g1 I/ q$ p$ z/ ]' H0 D2 H! d2
& M! G/ c" H8 N% }& D2 d) m
什么是插入排序？

顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
2 Z+ L# W  Y" Z+ R
0 g( ?1 Y! M# s. s1 D; ]$ _
, W) {+ K1 T8 `0 b& j, w3 H
4 a3 G1 S5 L, E) ?+ B, M$ Z! c3
5 b: @; L% C  J8 q2 X4 [) v6 r
: P2 }) X1 I; a9 L% ^如何实现插入排序？
; u1 A1 g/ x" l$ M$ |6 z
, q, f% F) B& x% O上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？

9 @  u! |8 h' `, {, s0 F, K; C, G

1 H: [$ {5 |% k/ _1 b  E首先我们要将数据划分为两个区间，已排序区间和未排序区间。





* H0 p2 \; `+ g6 X. \6 e我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。

/ t: p4 x# t- z1 D
/ Q9 V$ E1 X# z, @) [0 O
) E2 m6 {% I5 q/ t# w, L% }

; m( I5 }! [" {9 }! G& j! {如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。

( V& r9 x' z2 g


! _" v/ P9 ~; ~5 B
+ J" g; i1 |+ Z& t最后我们看一下总的插入排序动画和代码实现。


3 y6 v) P9 n' V! P% [
; Y$ j$ w6 J( \0 j) X8 z  @7 G4

插入排序的性能

- w( a- ^6 E, ^" n我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。

" u" W% \4 V& V0 V4.1 插入排序的稳定性
# P# Q5 y3 a- Y4 L4 h. O9 P
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

4.2 插入排序的空间消耗
% r0 A  f* |  x- j+ o) ^0 {
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
; }( ~3 B( e2 Q- h
4.3 插入排序的时间效率
6 l0 d: v$ V: v5 u/ B) J
. }$ R! O" D% \插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
+ \" F# _- k/ [0 E! H! F
# P# {4 `8 w$ e: t  V) V/ d如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

1 U9 M; M4 F9 S# O0 k对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
1 Q% G/ F5 Z+ J4 T. L9 }5 a. @) \# _
5
# U" H$ p0 y3 f0 F6 ?
' \: w7 n3 a! ^# R小结
9 n/ C/ H* F5 L( R* g, J( Q
8 F( ~0 N% \3 k7 q  B, h' F我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

! L  d3 a5 p# S2 f2 ~1 B我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
! J) I5 r7 n. R; z
: s9 y; R4 o8 W7 }元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
7 X# w1 N" j! \& `" X+ D9 n
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
, I" W/ W; {# _& m
  `* a: C8 s& a6 O1 ~, p虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

& ]; m( Q8 g+ X& N& s; J对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% B8 O; |# m% \( s! D5 X0 U4 X& {原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708

/ |5 ~6 _: c) @$ C9 R7 t! @4 y