数学建模社区-数学中国
标题:
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
[打印本页]
作者:
杨利霞
时间:
2022-9-13 12:30
标题:
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
动画：面试官问我插入排序和冒泡排序哪个更牛逼？
+ S p2 ]1 O4 A# ?5 a& O! ]+ i
- ], J2 q: q, L: Z& I P
写在前边
# i4 e; S- H" S
4 ^: S8 W! \7 g: K* S6 G
4 M: x9 t. Z+ H$ ~) Z, d" C3 @
排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
' }0 f9 d0 J' V
6 G/ i' T9 g P; ^ ~8 y
虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
, k; G: I" [+ a- b% F) G5 p$ _
6 O0 r6 U: h, g
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
- z# L4 I ?' @( @. M* X% M
* h7 s) v7 n$ b8 O Z7 {- h& Q
思维导图
$ w6 E1 L; K; y/ w3 L! z* t8 [4 u
# _+ g z$ T% m/ p$ \5 h- Y" h# `
" V. K* [# L. C0 A9 s2 K. _
7 h+ y/ E3 c. A* F
, A; m3 L+ c; x5 Q {
1
! A5 Z# K9 J- d2 H, V
& H8 ?) o( t/ K0 F) |9 W
如何分析一个排序算法？
& a5 m6 A& V; A6 u
6 R; b/ O. i! \2 k8 y
之前写的一篇很详细的文章。
, H! s( ^: x8 N
, B3 z3 J* d' l
佩奇学编程 | 复杂度分析原来这么简单
p2 K8 L, R8 s; F6 N
( ]& F* x9 P0 x( [/ x: R5 e
分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
5 A7 x" k/ m. G1 H% S9 n8 u
: K- y3 `- N) V4 ?8 |% x5 ?' A
1.1 时间效率
4 O+ Q2 U0 f! Q
$ D2 {) R" t0 l- |( @" Q. @
这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。
7 Q. E- h. u _% X
( W8 Y$ b8 }- g4 D% f- y9 p
复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
, E- O4 s1 ]7 \1 I" R
. z0 f8 h( j. [# n
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
) E$ u1 {; f8 u6 s
6 F+ L# g$ j' N2 t+ z/ k0 }
1.2 空间消耗
, ~# E0 i3 u# E( `5 H
% `) K/ ?9 E6 t
所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。
& ~1 x& f0 i" y8 \7 F
: F( P! l2 D- U' G) B O0 H; f6 n
注意：是额外的内存空间，存储排序数据消耗的空间不计。
" {/ Q" t! v1 p, i5 ]' ^2 @# _
; p. F; K* N3 t0 f3 p
1.3 稳定性
?' y2 m$ j3 |# f& @' L* D
! Y" b; ^& _1 @: U
算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
& P( D. \" }7 h: o5 R' m! k
, {* i* s0 Y' f J4 [# q/ p
2
% v f' U; H8 Z, w' R7 `8 l3 K
- G. s( Q4 x3 ^7 l# Q. O
什么是插入排序？
- [) n7 o3 o+ `3 ?( W' ~
I7 V/ s* _+ m
顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。
6 i7 A5 ]4 i5 Y! K; a) Z/ A
( ~- J$ m3 G1 j1 c" {7 t! v
2 \* \" t1 F. U2 N7 n$ f) ~
( N" [4 |( |- u( d7 H
3
4 `6 c+ H- S6 q7 L$ o* P0 B7 H
9 d4 H& N4 G) i4 _4 [
如何实现插入排序？
: n# M0 Z# s; n: W
% p4 W( `; \! G* J5 m
上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？
7 ~" p! P4 a* t
$ J7 u3 }8 A2 k8 B
& e" M! b ~( o% @( e
! z! y4 e; n% s
首先我们要将数据划分为两个区间，已排序区间和未排序区间。
! V7 X6 w. A3 M- }6 d0 J7 O
7 p' x. y8 q2 y. g6 c
+ q0 X* y; [0 F; o6 b9 j5 `1 G# ]
, [; z9 G2 h: j8 c( b
5 ?, |7 Q2 V7 ^ V. K
L- n$ g, W7 g% w
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
8 b* l' i) ] U+ b! F+ w& x D
. e. {5 P/ F" u" b5 `$ s9 L; e* S
, u% h2 d# g) [
$ E. s* [1 U9 N" T8 D7 [
0 _9 W9 R& P$ b6 W
, ?! f, |% g$ i$ K5 G
如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
+ K# L+ ^ s$ m& _' u- ?
5 v3 a& v6 \2 L3 o2 r
. ~$ I9 n( m' n- b
G* |1 ^7 v K9 c' {
! n# O% h. k2 e) S9 f1 Q: t% w
. s: ?" v% L6 {
最后我们看一下总的插入排序动画和代码实现。
5 N/ l* O5 P0 O* r% r' |" y4 j F0 q
, p8 r) Y: v' k; R
$ p& u* f9 f& Q( `# G7 u
% @" L: Z# P6 v
4
! A/ |9 B, B1 _/ [
: X) m" g: N6 n, q
插入排序的性能
# O* p6 X" l2 l0 t+ N. D4 I
+ P+ |. X/ g- X- G! ?3 M
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
8 E5 d8 ~) O J* G4 b; V
, ^% P2 Q. N! T3 ]5 }5 n
4.1 插入排序的稳定性
* r8 j- d o. L: T
' F- L8 F$ K- A/ w. C9 F
再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。
/ O- v" }/ K) j0 g( J
1 G2 K0 V, K7 M* u- u, R
4.2 插入排序的空间消耗
5 L- S* P) z9 R( n/ t" K2 O
, {" H! |2 V1 f4 J- B
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
$ q+ i& j. S5 b# z- ]
3 ~: C. g4 L! r% g6 s' Z u
4.3 插入排序的时间效率
3 v7 U u' C. T, T5 r6 x
, P. v" R' y* |8 k1 |
插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
3 y. G" u+ L0 b) l$ W) [8 N
3 f% k% S* O0 [! B! a, [# U6 T
如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
4 s/ l) L, s' M( @( C7 U) S
1 R6 A: [- B. h, ?0 [
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
4 ~# s7 f& d: ], p
) Q+ s6 O E* ^+ Z: F. R3 T
5
o2 j- P) f, E$ |' f
, m: W: U9 h! V$ G
小结
5 ]5 n/ Z0 N8 m* U5 V
8 K- E+ r x! g5 U+ E+ N* S
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？
- d$ G; A9 l9 a: [
" [, i. n: x0 p4 Z+ M: Q9 C/ @
我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
3 P7 [2 c0 P" g" U: }
. m+ t: T1 i- ]3 w" _7 d+ d
元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。
" Y+ S' s. p: E0 @$ O2 O
+ O, ^4 K/ u0 z, K. L1 Z
有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。
5 e; D7 ]: n- z2 ]9 ]2 P
! `' o; K# _3 r, u, [) O
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
$ \! l6 d7 Y- }3 l
" T: D9 ^" W( v! B n. x0 F. ?
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
2 ^7 [& ]( R$ x: S( K- B; I
————————————————
4 v$ A$ w6 l7 n @6 y$ L
版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* \' u: r8 i5 e1 z( L( O1 a8 v
原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
$ v$ J2 u3 ], W2 Z* l! d3 ]! _1 H
* E% U; s# U4 r0 j( w
7 I" a. w' H7 q" q/ f* s! E* }
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5