- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 81
- 收听数
- 1
- 能力
- 120 分
- 体力
- 542810 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 168221
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5324
- 主题
- 5250
- 精华
- 18
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
动画:面试官问我插入排序和冒泡排序哪个更牛逼?- L7 Q9 ~( v4 U: j
; w4 j* V* [8 c) m% Y5 x3 r0 |写在前边- M) h+ n# N' a3 D
' Z9 K' B' W* B4 T4 X; c9 a6 |
' S b& z+ x: a排序对于每个开发者来讲,都多多少少知道几个经典的排序算法,比如我们之前以动画形式分享的冒泡排序,也包括今天要分享的插入排序。还有一些其他经典的排序,小鹿整理的共有十种是面试常问到的,冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。3 r' L$ _; e* H
% b' m4 [0 Z2 }6 A3 C' X
虽然我们基本知道了这些排序算法,但是在实际项目开发以及面试中往往出乎我们所料。在面试中,经常会被问到各种排序之间的比较;在实际项目中,往往排序的数据不是我们所练习的整数。' Z& Y9 X2 Z9 i* C: x3 {
u" j5 ^& B; H" I8 M) q4 D8 i那么今天我们来学习一下,插入排序比我们之前讲的冒泡排序有什么区别呢?面试官问我们,我们如何回答完整呢?/ _1 D$ h3 ^: A1 N3 {3 n: a( |
2 g* Q7 S. y, D/ f: V x* H
思维导图
- J; O; S; x0 m, r2 S, ^/ {
$ m4 j' D2 O6 J; l- j) `, y2 l/ f6 {' l1 G2 u' e# P2 ?& @& P
6 `' X) D6 v6 h5 x/ n% f
; A8 S; ?1 @$ y! ~1
% o. I* Y5 s2 e" F1 M0 Z
) n5 d* y5 Y7 F2 }1 ^3 \# j如何分析一个排序算法?+ \$ @5 Y. {8 O7 g
$ C- H1 J) Z1 c$ ?6 L
之前写的一篇很详细的文章。: H8 D9 h; ]0 V: O8 t
( `& }6 W# a- c3 Z6 s2 {9 J佩奇学编程 | 复杂度分析原来这么简单& ^) I( d& J! m
) [' o3 a; J/ w+ M. [! K$ R5 S: }5 B分析排序算法已经成为我们衡量一个算法优良的重要标准,从以下三个方面入手。
5 `% Q' v% F9 E( x5 M3 l& x- ~0 m# E7 E
1.1 时间效率6 b8 p( B- g! y' X; T& K& e
% E$ a, U# Y5 X0 `这里所谓的实践效率就是时间复杂度,相信大家对于时间复杂度并不陌生。+ S# {8 Z. \2 N0 B
2 ^- b/ {+ { Y8 y- q B7 z! R& S
复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
0 |9 }8 }2 K" p( Q! y& M8 z7 i$ R0 j |. R+ C6 m0 K2 C# \: m
对于时间复杂度的分析,要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来,分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。6 }3 T1 t6 X' }
: W4 V- B: k5 x+ |6 p% l1.2 空间消耗; \) N9 Q6 H+ N- I
: h, t. y/ {& h { w所谓的空间消耗对应的是空间复杂度,在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1),此时该排序叫做原地排序。3 A7 G A4 ~# y1 E5 R" h$ A! K
8 g7 k! A# k( d) N1 {- ^2 Y/ o q注意:是额外的内存空间,存储排序数据消耗的空间不计。
) C5 b7 @5 y: H4 |; C) j! d% p2 L6 k9 l) Z: `( ^# q
1.3 稳定性
( P( [" |# j8 x" _* f; n9 \$ Y- Z+ A& x
算法的稳定性虽然我们之前接触的很少,但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢?比如有一组有重复待排序的数据,排序前后,重复的数据顺序不变,此时该排序为稳定排序。否则,叫做不稳定排序。它在实际应用中非常重要的,今天我们就不多说,以后会慢慢分享到。
4 C; ~3 W: u7 @0 ?" W/ _- X$ T/ }2 z
2
3 N0 m# ^ ?) d/ h# g) r5 V1 {# g- y
什么是插入排序?
8 W; ~' g' s: h
% O _5 B) x2 f) R0 C顾名思义,插入排序就是通过插入的方式来排序呗,最经典的就是打斗地主,可以将打乱的扑克牌作为未排序区间,手中已经排好序的作为排序区间。每次我们摸牌的过程,就是从未排序区间,通过插入的方式,插入到已排序区间。那么这个过程就称为插入排序。1 O* t+ O2 n; |
9 e7 C- U' H& X) K+ P
) n# X# X2 j$ q" o8 G% m4 B$ r1 a( Z2 o' K" P' t) e
3
' \1 d) B8 U6 A9 k! b# r2 \
5 m' e5 g/ W! D5 V0 E% M如何实现插入排序?
1 h% Y r# u9 g5 C* B; S: W3 s. H. G7 @2 O2 l L
上述插入排序的概念我们已经理解了,那么给你一组数据,如何来进行插入排序呢?
& v' q' U, x# z* h3 j7 j: m D5 R+ d! N- w7 \
+ c( L4 X3 a. n3 n% b& n
! j5 Z1 q( A8 Q! r/ }+ y2 U' M首先我们要将数据划分为两个区间,已排序区间和未排序区间。
& w8 K; t& _7 K$ r
$ T L0 W* c4 i
3 l1 ~; g3 B. m* i3 b# q1 |6 Z* N( Z4 ?, i1 g% Y$ E3 I
. B* A# [1 X0 @6 v$ V% U# @" D8 G6 j0 M2 I7 q2 d" X3 p
我们从未排序区间取出数据和已排序区间的数据进行比较,如果小于已排序区间的数据,那我们就交换数据。
9 ~( | E9 F5 P9 a' x; U
% K) h: q% t! r9 G6 S; r2 j0 O# j! l! f
1 U( H9 O2 C( D4 J( c
3 d5 h' ^: ]) O' |$ r$ \
7 {6 h9 ~* a" `+ @" A3 Z8 e如果交换到已排序区间数据不在大于插入的数据,然后将元素插入进去。
: R6 O. d" s2 w- N- C( I t G$ b9 }+ k- p- w: s C: n5 m( R
* @9 n: o Y$ j/ E6 M3 k
! z) d: c( c0 I- j/ {: N
9 d! O2 @) `! W; m# o6 v( P2 n' z
/ e; E: W$ Y& P4 J6 i" ^最后我们看一下总的插入排序动画和代码实现。) C% j( V. \# Y; B# x, \: c- ]1 M
+ \ l% A. ^; I9 J) y
: \; K9 U+ ~9 {6 Q; ~
/ {! e& o) `3 }; v% k4' L- d$ q: r3 e& @' K% {& X% m) y3 d
1 e/ H, b9 d+ @
插入排序的性能
- b% F! ]' d0 T+ z
& R! {3 s: n: G; ~, F& ?1 p) ?我们通过上边的对插入排序的拆分讲解和动画以及代码实现,想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够,我们在实际项目中,还要考虑插入排序的性能怎么样?因为才能更好的选择适当排序应用到项目中去。
m- h5 M% X) r5 l; T. Y/ g$ z: n
$ _9 y! M0 M0 E) g3 S/ |4.1 插入排序的稳定性9 T5 Z3 K) _; {0 F+ Y2 M5 Q
/ {+ T2 B+ v! S" u4 z
再插入排序中,如果存在重复数据的话,前边的元素再插入的过程永远在第二个重复数据的前边,所以插入排序后的重复数据前后顺序不变,所以插入排序是稳定排序算法。% e' c4 o2 q7 H& l
2 E( I# J- h: s( X, ~2 ^# A+ y! }9 X7 d
4.2 插入排序的空间消耗
4 x: \& t3 R3 T" c* j/ }( Q- E3 ^( n
我们可以发现,插入排序的移动方式,需要消耗常量级的额外内存空间存储,也就是代码中的 temp,所以时间复杂度为 O(1),我们上边讲到,空间复杂度为O(1)的是原地排序算法。/ F/ B/ X! f% v4 E7 w$ q8 X1 g
, b. h) G( q* j, `, R8 t, \. y
4.3 插入排序的时间效率
4 `/ g7 a3 p$ s; H" p9 b. R# y" x, h+ B6 u9 H( U( o% q o3 ]2 ?
插入排序的最好情况就是不需要搬移任何数据,从头到尾寻找插入数据,每次只比较一次即可,即一组有序数据,所以最好时间复杂度为O(n)。
6 q5 R5 M$ z, ]' j% R3 w
) _' j5 y9 l2 c _" e8 H$ a" b+ O如果一组数据正好是倒序输出,那么每次都需要比较移动所有数据,每次移动时 n,n 个数据时间复杂度为O(n2)。
, |2 B" y+ k2 y. l6 _
$ {9 `* \4 v2 T对于插入排序的平均时间复杂度,每次插入都要移动数据,插入 n 次,所以平均时间复杂度为 O(n2)。: B/ t8 K$ u+ a' [, |# M# o H
2 l6 l. Z, N3 X# y3 n1 u
5
/ a' W3 r5 ]! C1 q; _
: X5 m* s C4 p8 j0 D0 J小结4 p1 J0 N0 R' Q; `
* ~3 L0 y- o- Q; b! v
我们学完了今天的插入排序之后,我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢?
3 A' F. w8 ~6 y4 r1 F# q
; I1 e6 [! u6 P我们现在元素移动次数上进行分析,如果一组无序的数据通过冒泡排序排好序之后,它的交换次数是这种数据的逆序度;对于插入排序来说也是一样的,移动次数上都是原本数据的逆序度。8 J/ Z& w6 @, M+ b
7 q" j4 |: {7 b# M8 H
元素的移动次数是相同的,那我们接下来看看元素的交换次数。从代码上分析可以明显看出,冒泡排序的一次交换需要三行代码,而插入排序的交换却需要一行,所以总的交换次数冒泡排序大于插入排序。. t# w) y+ f6 m. x
& m6 b0 I2 q% P, A# L有小伙伴会问,这两行的差别有那么大吗?移动一次,我们可以不计较,如果数据很多,想想下,两者的效率差别很轻易的就比较出来了。
5 Y" B. {; a# l: |& m8 l/ x( @ Q0 `0 i( }1 h% v2 A2 z9 e+ h: B
虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的,但是我们实际使用中还是优先选择插入排序。
' n4 {6 v7 t3 R% a# ~- s( P, q; l8 V$ \* b% A9 z# U
对于插入排序还是可以优化的,对了,没错,就是希尔排序,我们在这不多分开写,后期会继续更新。
' b. s O$ J6 V————————————————
* H6 u G9 S$ b. }8 S7 f2 R版权声明:本文为CSDN博主「胡鹏程的博客」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。; C8 f1 t7 x9 ?$ W4 }! K% \
原文链接:https://blog.csdn.net/lyshark_lyshark/article/details/126792708
& G, r: U3 D0 |; t
# i6 {5 R$ S& M+ r+ N/ C
9 o% C6 l; y i& O5 B- k; ~ |
zan
|