数学建模社区-数学中国
标题:
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
[打印本页]
作者:
杨利霞
时间:
2022-9-13 12:30
标题:
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
% @, _2 k0 V- {
- F* N7 _( s" v" L- |* l, ]
写在前边
2 h' u6 e" L7 c- Z* ^4 V
% L5 o) {$ @0 ^: _% l% V! s. t
$ ]6 o2 M; t" s
排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
; ^5 p9 z+ i& p) s7 \
- O7 ?* {9 r$ W" x5 w4 Z
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
* Y" N% L2 H. e5 Y" n- o
/ F, h0 w( h- k
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
# |1 h; l* y% u0 |* K+ p2 K
4 }& r" B) q( h
思维导图
# \# \9 f, ?% R2 p
6 E0 G8 {, @) H+ n. T) S }3 H
; t, @( V* y; ^$ x6 l; B% {
: o- |- H6 t: y o! u7 q# w$ v2 [
/ r& K1 C! K5 I7 r# N
1
$ c( E0 X, c5 O# v6 _1 V
% m, |9 S* ~, y1 x7 e' C
如何分析一个排序算法？
5 _. ^: Q9 @& o2 A7 |/ q- w
3 \- v8 D W: \+ d, {' s
之前写的一篇很详细的文章。
$ Y5 d* e( @4 b, l& O2 c
0 d6 \& z' L: @. I
佩奇学编程 | 复杂度分析原来这么简单
; J5 h) b: E) F. ^, f7 Y `: N
) ]% Y& S" ] A" e) s
分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
" n6 x4 X b; [0 R
" x# a M4 M: o" }2 O
1.1 时间效率
4 r i' T0 z( F+ T, y! }& m( U9 r
5 Z/ P2 {$ g8 G6 b6 d
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
8 E3 ^4 d4 Y: I I7 n/ Y
7 M9 X# A; F: v
复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
; {# n, w- ]) Q
# F; C# Q& `7 D7 f
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
+ W7 q- a! x u$ C
$ H2 o5 M. E* g* {# w5 \
1.2 空间消耗
) Y* Y; @6 ?; S5 C7 v
8 H' K! V/ a: Q+ O
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
, }4 l) r/ x3 ~7 i! G
2 C' R" a& y: y( ?, E* D
注意：是额外的内存空间，存储排序数据消耗的空间不计。
& r. m, {- X. p6 J
. a+ L2 [( o8 z+ g, ^" b- D6 |2 t
1.3 稳定性
9 U; W- u( K a$ m
6 H9 |/ T8 T) l2 |; |6 q& a8 V
算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
" `$ o' h+ O+ k& X6 `6 B$ K
% B7 p3 X2 Q% T9 o
2
3 w& R# q% [' C( o* V+ Y0 F
4 D0 s% I; c0 s( k, F3 Z
什么是插入排序？
8 D( ~) P8 ]) p
$ @6 g; D" G* ?
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
0 S3 B: L* a8 V/ |7 T
5 H- m8 ] L w6 Z* v
; w9 A% y+ U6 r8 v g+ [
6 A# m( S2 }2 _) q) e, W0 e' x
3
' M+ q9 x! _; m+ s) K) ?2 f; u
5 o E( [; a9 L) y0 u# i6 c
如何实现插入排序？
$ e/ \0 T# _3 x$ Z; Z) j& u5 t0 w
/ n% d9 J V1 ^( n" n# H0 Q- S; h
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
$ {2 F/ [$ e4 k2 k. ]% S5 N( ?
' o1 O; I* i0 E o: A" k6 S3 z9 F
0 A+ f+ d# Y+ Y" |: j" V+ K2 n
$ ^8 j& J1 j! F0 E
首先我们要将数据划分为两个区间，已排序区间和未排序区间。
- Y- Z' P0 ^1 v! v* o n
! Q1 ]) k- ~* E/ T/ O/ U+ T- F* [- x* O
# m5 m( F: } e" `' [* R
+ j" x9 f* W K' `7 h. x
; P: c" B! F2 K1 t7 x' @
5 c8 P) t6 r2 G$ i6 f& K9 R
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
8 \0 I& |. l% I* Y% [2 }
& l. R% z4 T2 {% X R4 b
6 ~9 D7 e" ~. E/ V
) e6 ^# F# h9 Q+ w
* P7 B8 }: u) G6 q+ D
% k* ^+ p$ T- n6 [) A) i e5 k
如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
) Q+ w; f' d# Z
# A9 {6 R( h& m% {* g; P7 o
9 u) L) ]- f4 {+ h
" Z' a8 b* m+ E/ ^4 m
+ u5 e2 e' G; t/ D; a- X# h( {
F$ R! X2 G( w- _+ i! E% ?# y( `
最后我们看一下总的插入排序动画和代码实现。
K3 @6 l( x1 ^0 M5 ^- c, N
t* E% N) d; s9 r' N7 `% V. z
* A/ f; h5 u5 i+ w: O- p2 K: ~0 A& s4 U
" Z, t' o0 [5 q
4
3 r1 E G/ f% K8 v( p5 c! k
( C+ S% ^5 L8 C5 C: \% c
插入排序的性能
# d% {0 l6 i. E0 h3 `' o- a
' d5 R' V; U4 k% H3 w
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
) `/ x9 v' _& ^, D" N% H2 @0 D3 A
, \; H; ]3 G, c, W) I' Y
4.1 插入排序的稳定性
$ q/ ?- e: V2 t0 b
: |8 c6 D& B: r
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
' X' `: w5 ]+ a Z5 }
; V8 e6 {3 H8 {) M+ n$ b
4.2 插入排序的空间消耗
: ?& d) R4 o- q2 a9 O; I
4 p; ^* ]& t- ~; v
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
; C. E6 `( u; w1 U
1 G c$ b( }' r) j
4.3 插入排序的时间效率
0 ?0 N. P d" k2 u
2 S7 |9 U& N% S8 w" ]1 D
插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
; a* E" q" o+ k/ b' J8 T+ V0 \' e
4 I) c$ w0 P2 ^; E( ^
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
) ^, s" J1 ^! a9 B; V
1 W3 h2 }8 `0 B- w4 Y
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
0 ?5 t3 I b" w! t, j
4 v. e. A! G" L `3 B# X. O f2 K
5
; m! x. b; y4 s
; C* U2 X: I1 p3 [* N" F
小结
1 c8 K3 j2 Y$ Z8 j
2 `8 q- {0 S3 {" s8 x
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
" W$ x- @2 I& ?4 }) O% b- z8 `
) w+ p# s+ C* ^4 @( D0 v2 t
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
$ \2 h2 d4 f) @/ \$ o
; Q! `2 I/ S+ y3 A$ C6 ]6 r
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
s! n2 D# x6 |8 o2 d
3 \+ ?1 e. p: q( B! k1 o+ |' f
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
: S9 ?, d* ]; W8 c4 U
/ }9 {) l& F3 i1 ~- Z1 C. A
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
' ?7 i9 t6 p9 Q
' @9 u( w/ }# x7 e3 L
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
$ _- {& Q- n5 R% F+ O! O
————————————————
( I# D, Q1 K" H& u2 ~ V2 F
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* B* U* M7 M/ ~$ k$ N
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
/ X7 {: X! n0 T! \% K; c
) Z* e- ^+ L, @/ X0 _! P5 P0 w2 ~
/ g/ b, T8 t" c2 r7 E0 W) t* Q, b6 M
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5