数学建模社区-数学中国

标题: 动画：面试官问我插入排序和冒泡排序哪个更牛逼？ [打印本页]
作者: 杨利霞    时间: 2022-9-13 12:30
标题: 动画：面试官问我插入排序和冒泡排序哪个更牛逼？
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
+ r$ L5 R2 z6 E! r( i1 U  ]) j# N$ V8 s: n: d- d' P
写在前边9 a% k2 N2 C; T( H8 U/ a+ y

' b8 N- r8 q1 c" U
. Y5 x, i+ Z- r. s排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
. Z% p  R2 X9 h+ T
8 b) m9 t6 F! Q- ?3 A9 M- z" a. k- ^虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。1 q  ~- [* s  J# w

" A3 G1 D& ^" k2 n1 j那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
5 H7 \& ^) b# P6 c1 B! R( X
' L4 I+ ]9 K2 g% ?3 Y$ n. ^" Q思维导图
, J) b9 S3 \4 s# O  ^" s
* `1 z! n# p6 e8 W! e4 [& j4 X
  \5 {5 @  B, L0 H# x- L! Z

  d& p; t# H' @; Y9 c/ Q, x9 l1. E( n" d. X6 |3 b+ {! D

  Y6 R5 v8 n7 U6 f$ W" }! d- `. R如何分析一个排序算法？
4 ^: `$ c, Z4 p) g% G( E1 Y4 i* |9 j. a
之前写的一篇很详细的文章。/ |7 }# I% B& {5 }$ o6 }

2 j& i9 E* O* J; g7 a9 {佩奇学编程 | 复杂度分析原来这么简单
4 e; b# }5 S/ q8 _  X
& s/ d: q- R/ y分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
7 O8 \! u1 I: V( L4 y+ V* _% G
- y2 e: _, ^8 j8 G9 f1.1 时间效率2 v7 c* i" c) P$ N. w
8 i9 u, Q  [' z' E
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
( r6 u- Z/ {5 i$ j( L% d; R6 P7 {6 F% n
复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
! ~9 I: }: @" t* D0 [
% x2 p/ y* y/ w( O6 K0 i对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
) P1 c5 {/ p/ \; i- d6 Z. Q+ |+ i6 i) p
1.2 空间消耗2 M  j* A% H4 ^) N) x
7 R9 _( _+ d# Y' i5 t3 Z4 T6 w
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。: _- w3 ]' t8 n

8 P, [/ m8 m+ P& a注意：是额外的内存空间，存储排序数据消耗的空间不计。
! [8 ], i' [0 a' ]$ l; m0 `1 R' V
1.3 稳定性
8 a$ j2 k% T, p* P" @7 x- U! ]) w2 {& {: f
算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
% }4 ~& C8 E* v7 Q
. q  e* F0 m% R. i3 R# m2 q7 a$ C* ~2
% O3 ~) b- i( }' r8 V
* g3 T0 e, F+ F$ h什么是插入排序？
7 L0 S2 E3 z  @  _1 d
2 z$ T* g+ r8 ?5 ~( e5 `, ~顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。5 r( d2 f: z0 h' U

1 A3 q/ J# E  t) p& w
5 C3 e# T) d/ h, q
9 k9 B% g7 ~- ^: d1 t' x3" x+ d# c1 Q5 v+ \

9 U# V, d; u2 u8 f, Y如何实现插入排序？
& M+ i5 i% E5 V5 q% p0 N! K/ U, F& y0 E% d1 V+ o2 T" R- X
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
# ^0 n* @& Z: x; s: n
, c) m" p% z& T$ N/ o9 U: O) S& t/ p8 ~3 Q, P

3 H. X* ~) l- e' F4 Q5 B7 ~首先我们要将数据划分为两个区间，已排序区间和未排序区间。7 ?5 S( a+ D" ~. ]

6 H4 \, j! L7 N5 W0 j
  [/ e- }+ A$ Q" ^. @; [+ O0 l# Q) Q1 Q7 z! y- a* i$ B
2 T( r! I% @  j4 ]( N- H" h
8 n' G4 B7 `- o1 Z: p# u/ K
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
2 F4 g$ h& s8 ~3 ?9 f- d+ ?
. E% w0 ]! ?3 G0 r9 E& G5 E8 H/ P9 M" e* i: g; D/ g) v

  ^' g: V3 ~' E* E+ m. W0 n
( r: x) V0 T* T) E
4 K$ D' J( n5 N6 z如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。9 V: Y0 X! u9 Q3 O$ A' s
5 S+ q/ _8 ~2 I! ~
9 L# F! y0 o$ e1 o4 c
- k- U2 W: d7 U) h; [# T( C4 q; f

% K1 N% L1 w* n. J. l
1 Z. _5 k9 L1 `* y6 y8 F4 }最后我们看一下总的插入排序动画和代码实现。4 c! f2 e) i* H/ @4 I- \& n

+ @! R( X( d: k  R2 [1 P7 N
2 X' r# ?! {; r4 m, E8 T! n  j* `6 F
4+ q1 n/ `( o0 P+ ~

! h5 i' ]4 a1 K) r+ t2 e插入排序的性能
& A( u/ r* @; d- i5 f
' P% G' D: O: A3 m, \. ~$ m我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。0 r& Q# [; S& d' K! v

# h% D* x7 T, [9 m# j) |4 U4.1 插入排序的稳定性
6 i, l$ @) ~, n# ^: x/ i8 F, U4 f8 M, s' N7 `4 C# Y
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
! s- X' c5 d4 f9 v
9 K/ R7 `1 m; X& a8 K, ~* Y4.2 插入排序的空间消耗
) i# t4 g  m4 r6 ^7 J. Q* f8 k9 Q) c" j: q1 j2 h
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。+ c! |! `+ K; `1 D+ I
# e8 o" R6 Y* }( i
4.3 插入排序的时间效率  g" }& ?5 f3 @3 O6 @: ]. T

3 T! e3 v4 I( e- [: d: p0 H插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。# x; l4 D4 x1 F! T

9 B& ^  }/ w' R" e: F" P( v如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
" y( l4 L2 E& m- M3 m# {' Z! ^6 W, x  K" v  X, A- ~  y
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
- w  d  c* Z# y( X0 a5 j. u0 Q+ p2 B9 Y7 X  j4 u
51 w8 p- B. J5 d8 |+ w1 q
* `2 K; T- H) A/ S" l0 n# E$ ~
小结
  M/ J: R( @$ i
" i3 f# T0 ?5 K: {我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？. s3 C( S! K: Z" h
5 D- a' |6 l6 |; V; C* x
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。" P0 d; R+ `9 |5 S. b  E& R2 R. X

$ l6 }8 x- V; g+ ]元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
% B# y# a. d6 S2 I* |/ B% I" z- s" _3 }  Z
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。- _# v. i1 C$ U

8 s+ e; D/ z* X, `7 f虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
: h4 G  g6 z5 Y( V  j$ Z
. y+ n- J6 k( @对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
, j* c  o: P3 m, c————————————————
& U% G$ B) w8 v, q+ |$ G. ]  G, `版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
$ r' f- l6 \& p7 {1 A原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
" y: E. B+ q  F4 R6 l* e: o  r6 p0 V; L2 B( ^! k1 |& }; ]
* \* g0 O; e& V1 `




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5