数学建模社区-数学中国
标题:
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
[打印本页]
作者:
杨利霞
时间:
2022-9-13 12:30
标题:
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
3 I; S9 f# D0 s; A
: n( M# @! ?3 ~- G( L2 f: o
写在前边
& V, J# @0 ~- b9 m
0 [3 @4 V! z d' ^
8 N) h0 W% A+ o& r5 p1 V5 F
排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
. o" o& p4 |3 ?
& r! N5 u0 k. F; p
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
" o$ I h" l. w$ Y5 h! G' u
5 |6 ~; S2 `. v, ^
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
( b& G3 ]: N" U8 e* M7 K
0 Q2 `7 `: h8 d! L
思维导图
k- \/ M9 M& h7 [+ \( a; J7 s
) H: t) t- L. J" g
- B7 Q: ]9 `2 V6 g
8 J3 ^6 Y: i; |; }" e1 q4 A
1 `/ W6 K& z" `" K, M
1
& {, X) Z3 U4 E1 u; `. [8 y
& Y2 t' ]5 V6 u' v* p
如何分析一个排序算法？
4 E. e) g( k* U3 v! p! z
7 I0 c$ `0 S6 k& V8 ]
之前写的一篇很详细的文章。
: S6 H7 Q4 r% M# R
1 h( U p. G `1 k
佩奇学编程 | 复杂度分析原来这么简单
- n( t2 ^) B- R
- W. W. t* {! x9 Y7 Z* [
分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
: s. K2 ^: h, u5 D& J4 s
; v' t7 z8 A8 z! O4 _+ V0 Z
1.1 时间效率
" F% O) v7 O6 m7 W9 }
E! X+ f9 f- N: N: c7 V) c
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
+ p( v" c% a4 v i
2 G% p% q$ V) [
复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
1 B% ?. D3 h) Y( J
- O; e8 V# E7 S/ w
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
! `7 N+ P" Q9 t5 w
, T. N0 B9 O8 R6 G$ T2 z
1.2 空间消耗
% ~- k+ e; C) M4 H* F7 u
' g! s; m7 { J( A$ g
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
9 w2 ^4 R1 `/ N& }: d
7 Y. r; M. N9 z- @8 B2 f
注意：是额外的内存空间，存储排序数据消耗的空间不计。
5 _; U6 V& v( m% A& a5 L
i8 H- U3 l) g O& ?: M" J
1.3 稳定性
( r+ [7 ^, l, O l3 u+ {( Z' y
8 J. z& e& C/ \
算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
/ s% v Q3 z3 z
. G/ n5 S' O7 N
2
4 [3 `+ O% b5 c: e4 ^2 N
* Q7 m6 w% _; m* q
什么是插入排序？
9 e. N: B" U% l
6 R3 {! N7 J- s8 @
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
& ?. j# A, j0 y3 T, `
) k& I2 o0 k8 E8 M! F I1 F* n
( Q7 i. V- m$ @& e
" S# a- ^# ?7 W T
3
% U& [1 l$ `7 |) t+ ?, K
4 y4 N0 u: @. n& m. m9 E
如何实现插入排序？
3 Y& e4 O7 e1 S' J( L
! I! o- M9 F: q$ R# B4 n. ~
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
1 Y) P1 m' e7 `
& `2 G0 K: V* c- Y' Z
1 X: Z0 E+ Y6 a0 a
' X5 R5 `# s; W; L2 G; W, I
首先我们要将数据划分为两个区间，已排序区间和未排序区间。
8 Y, T7 n+ L' ]0 S" U3 l
# u0 w4 @" N3 v6 F9 ]' L( p& o
+ S0 K: E6 I7 z" w0 Y0 l) M. s
- t7 a1 i5 A- |# B6 A0 Z0 N
R9 `: v& Q9 B, y
; i) b* K( |* |: g6 b
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
0 ^( E% c' u, \! j8 ~
% ]; u- d6 C( d( [
, @4 d0 I4 a& S9 U
3 Q6 e4 V3 u7 M Q' P
! a2 O; f8 D l, B8 u9 w
6 {9 u* a8 Q( Q8 o7 i: C/ N; s
如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
0 I( o8 }; F6 {$ Z* x* @& A
" g; `7 j& W- ]7 k7 _
; s1 b3 |: U) |
9 [$ V& z- q. e! }
7 Q* W* r3 t# h
7 s/ S7 Q; q5 ~7 M( l8 L
最后我们看一下总的插入排序动画和代码实现。
$ P0 j5 w8 R: e! ~2 D
0 x4 J; a k6 A: ~& e3 a; C
! L2 C: i% ]0 v r
& \$ T! x0 L( j; c' E& `
4
$ b% |- ~3 @+ j c/ a5 o. k
/ X7 w( D( N1 V2 w1 j4 K) O
插入排序的性能
# h8 z1 ? v, {2 @! c! Q4 R& o
B o* W) _) V* i! z' ]
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
# n1 f9 g2 E8 a$ \1 W3 }8 @
3 Q/ v3 I7 W' B9 V; E
4.1 插入排序的稳定性
1 G/ L: n; O+ N+ h1 Q# l* k
9 W2 h$ m6 |7 ^5 d8 e
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
@1 m% Q4 a- O5 D9 V1 R8 \' a
( N! h* p9 P; M8 J4 ^
4.2 插入排序的空间消耗
/ o0 H- [) H/ q4 w% E/ q
! u" W3 O, o/ G1 l1 ?! Q. w
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
1 S* R; ?( a+ F( }$ X
, M1 w: ^2 Y7 ?( J
4.3 插入排序的时间效率
- `0 ?, G2 z' C0 W$ d9 S' o) Q
8 V1 N& |; P6 u* q6 V' {
插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
- l4 ~9 }8 N8 c, c
5 a' i- X1 R! l; Q3 w4 k( e! w
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
7 m* ?1 l7 G! ~- _6 g
5 Z- k$ ? h; c" t- G7 W% i5 Z
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
8 d/ h# w0 d% ]
\4 d6 }- A% o- r* T% Z" Y$ L
5
* I8 ~' o8 H! L! c+ u% M
# u Y4 g0 R# X' I
小结
8 X7 D G u( R5 T2 a/ g- X
' r9 W R2 F) A" ?' ~' m* D
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
5 R2 c* ?% n& C$ c
+ X9 P" S, j" ] M/ b; [
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
& b/ c# v3 d6 P6 z1 F" o0 h' B
. X( i& c: J( c, p
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
# v% H% i) L# f% ~7 ?6 L( r6 [
0 p5 m3 m, I2 L1 K7 v" i
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
7 Y" `) B; |% \. I9 A/ V) _. i
8 B/ { B+ S. X, ]2 k
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
# @$ Y2 a# B1 Z9 _5 m3 h. e
+ w) ]$ \( g; c; n: ]
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
! x: ]5 [+ y/ a2 N! F$ h/ j# H
————————————————
: f; ?" T" V; A+ H) N, @6 [$ [
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
: m$ ~9 c0 D Z# h( f
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
) x' m+ k/ [, `1 l6 m3 Z9 G! T, n
E: u- T6 P1 U/ w
7 ~$ K" `5 Y) Y- F; u1 p, g
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5