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

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？
: x( |" {  n. O, M
. y& c4 a6 a) D写在前边
: g& Q3 `4 ?0 f8 S9 y, ~7 _

1 N: l: R! G1 c& }0 x排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
5 X+ b; s  Q7 d* W! F
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
& r. D0 ], T. ~2 T5 N# D# V
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？

* C$ @2 g$ ^2 s" Z" a) N2 {思维导图



( s  [/ B* ?% O: R1 |# e  _4 ]
1

, T  c% [! D% g0 k( Z, t% Z1 ~如何分析一个排序算法？

, P  v. K7 X2 W5 }之前写的一篇很详细的文章。
3 i4 j7 z3 }8 V8 e/ \
佩奇学编程 | 复杂度分析原来这么简单
8 D2 c# C& e/ O$ I5 O$ _0 C9 Y. z$ v& i
& b) ?! _& Z/ l7 N  N分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
6 L& U. H' M( ?1 t- w: z
" d4 t9 C4 [8 R1.1 时间效率
" A6 w6 F; N+ F* E7 L$ M4 f( q
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

7 V3 R8 Z6 c$ U/ ^( B复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。

# \. a8 E) p+ g% J; H( a2 H1.2 空间消耗

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
" x" V$ @: b, g5 }8 e+ ?
注意：是额外的内存空间，存储排序数据消耗的空间不计。

1.3 稳定性

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

2
7 C/ g" E) p0 W) @' D
$ J7 a' [$ Y3 R, [) i什么是插入排序？
" u! ]5 ~9 s. x" r
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
! y* V" a! y; {* [9 R
; Z+ p( T; s/ L  j+ q% \, s

3 C* ^: Y, Q+ Z% x3
( `2 \* U0 u! K+ @3 Z6 R: d% r8 o: ?
如何实现插入排序？
, \4 _8 a, Q( d' X' I8 S  p% Z1 G
! p! v9 b4 k1 h7 q, O& q上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
3 \% J0 r; @1 @0 V, O

% W. ^# S8 }7 y5 n$ g* G
$ |2 x( _7 M/ j0 d首先我们要将数据划分为两个区间，已排序区间和未排序区间。





$ z+ o/ \, t5 }/ N& F我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。




$ n' `7 ~7 }5 W9 A$ y
如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
# T$ B4 v% F; O+ n1 {) O
3 [! [' N' B- }, w! d
3 R* V: v) L- ]$ S3 |' k
2 x5 T- ~1 D7 W( v, P

最后我们看一下总的插入排序动画和代码实现。

6 R+ {5 q3 D+ `6 v, P: n
+ |( C/ ]4 Q  c$ {6 ~* o2 h
5 c) D# k5 B/ k, B# r! \4
& `( n5 k! c: D2 f- Z
4 n# ^; O8 Q/ }4 i+ I6 ]! N插入排序的性能
- n: ^0 N% g% j' d" C8 `
0 n  v: C7 ]' m+ l+ O我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。

4.1 插入排序的稳定性
. l! W1 \( b, R. o
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

! {& {: n; ]. t+ h: W1 I% F5 |7 z4.2 插入排序的空间消耗
' u) }4 c% K9 B) U. G) o
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
3 j9 O+ P: I% t# [+ m& x
: |& U! ^4 ^6 Z  e4.3 插入排序的时间效率
* M/ E3 m: i4 ~/ i
0 {. |2 o8 W1 B7 ?7 s! Z$ y+ F. ]插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
- D2 u5 k$ t/ A+ p
5 X% k% G  @- G; V( z$ Z如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
( d; ~1 V. d, C4 A' J* ?1 D+ Q; D
5

小结

% W/ T- x: H1 H2 \我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
' ]* g# L- Y/ B0 ]  e# {" o+ i
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
% [% Q/ ]( B' ~. w8 |4 S
/ {3 |  p1 k: |元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。

对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
————————————————
5 n+ ^. l  `% a: A- v2 \5 ]版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& V5 N" w7 d, d) g- C7 v1 ^原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708