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

杨利霞

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

9 R3 m- _$ |; Q写在前边


排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
& p+ r+ X: W) M' b7 E9 ~* I
- W  i4 e6 ]) E. m% b* ^8 d9 m虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
  e0 }; W% i: a8 W3 [9 d
5 m2 E; m3 m* u, z那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
! @$ n% v1 E1 c0 t; e3 K- @$ i
思维导图

5 T- O4 S% }2 M$ `2 C3 `) {8 d/ Q
  w6 k4 A( q& c

: V5 \, n1 |( D1 M" x0 A1
9 q: q+ ~- T% X( s8 \
; S& c6 @  J6 m! ~如何分析一个排序算法？

之前写的一篇很详细的文章。
8 l1 B# k& @  [$ n; w
9 {' j- U/ m; q9 N# o5 u佩奇学编程 | 复杂度分析原来这么简单

1 B7 C6 G5 Q4 t9 D$ n' t7 D分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。

% @2 v4 o0 e6 q# A1.1 时间效率

; B, j( u/ L0 S9 V7 d5 D这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
' ]; T5 L/ Q- o! Y# b2 v. }2 o) l
0 f! O" Y+ y5 u' k4 z# `复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

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

9 E/ a6 f0 b' N5 b$ t: I2 l1.2 空间消耗

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
0 H# t+ Y0 R$ ~3 s' @4 x* V) x& r
注意：是额外的内存空间，存储排序数据消耗的空间不计。

$ U/ w4 S& P) z; F* q4 L, @) R) s! J1.3 稳定性
% h& f) z" G+ c+ }" V
4 p- G+ V" J# @8 u; ]% c7 c算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。

2
1 o. s+ @7 V+ N  }
什么是插入排序？
& t* Y2 b4 h; N* z$ F
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。

% [! @5 ^/ \% W" x5 g. B

3
1 m6 V; H. V3 M
如何实现插入排序？
( Z! f% ]/ b' n, b( i& k
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
1 o( t- |# x5 J$ R' s/ U9 j

( p# M! p3 w, o* L2 W0 U: c3 s- R% i  Z
& t8 N! ?4 e9 n+ d首先我们要将数据划分为两个区间，已排序区间和未排序区间。
7 y7 k( P! [# O


  @5 \! o: G* a% J: Z9 Z
5 S6 v% c; Q; b  R0 }3 U, ^/ [2 s' [
# |, c2 y, u2 y1 g我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。



2 B% L; e. E2 H& H8 L( X

如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。

3 Z9 C$ m) d+ p7 }" E2 Y# |  U4 S

& `5 l! n; R+ X% n# s

最后我们看一下总的插入排序动画和代码实现。
: k! q/ S; U- P
, V* y$ V0 u: u8 }: t
# L4 l" l9 O* ]  g7 v& d
- K0 v$ ^% K* \# v# R4
: f2 @/ b4 G0 T8 k* Y$ N: {
/ B" R+ r7 ^1 x0 ?4 G插入排序的性能
. t* u+ l/ H1 S2 o6 }
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
7 p1 b1 K# A; V9 e) m9 r6 r7 B# N0 H
4.1 插入排序的稳定性
5 ?) ?" L- Z8 S5 f2 n% U# S- c; ]+ l
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
3 s1 b" r6 L% B1 h4 C" p
* {) h: z# n# a) x. \) G4.2 插入排序的空间消耗
% s8 h! P1 b6 p) ^+ T9 ^
% C# J. b. A& m; i* k我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
3 ]- @# X/ A6 T: f6 H
0 V/ m% o) T* x6 ~4 o9 ~1 Q2 a( A4.3 插入排序的时间效率
) l% P: `/ w8 X3 Q* i! u
, p% `9 }! @, s, k3 |插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。

$ p7 p% C5 V% ^$ ^# B如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。

! ^# j; w' x3 R3 H1 u+ {) Z& G+ e1 F对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
. U6 `, s9 W* [- A9 X
+ {3 I  `9 d- U+ l2 [4 M  K5

$ h) k  z  w, n1 I5 O/ S4 R" T8 m小结

我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
( Z% P7 G# C' S3 Q* D5 t/ V
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
5 }' s3 A% [  ?- m& l' S
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

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

, g" L. [2 p1 n! x! {/ ~4 t& ?! ^7 d虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
6 ]4 Q$ j" ^4 N; i! K- D# M7 H
2 T4 m! o2 H: E; D4 @. ]6 n7 L5 B对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
* o/ p' U' c! u5 R+ b- V————————————————
( K. q% c4 E7 w+ A8 B1 T版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' f! ^; U2 `. J+ K! ?' e原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708


: x3 }) p, l0 b+ {+ k; F