QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3041|回复: 0
打印 上一主题 下一主题

[其他资源] 动画:面试官问我插入排序和冒泡排序哪个更牛逼?

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2022-9-13 12:30 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    动画:面试官问我插入排序和冒泡排序哪个更牛逼?* Y7 [: F7 Q$ i) t5 o: l7 I: A

    9 R3 m- _$ |; Q写在前边  A' T! s, i7 _( g
    6 A& W& s! w, ?
    + w) I" g: d: `" V$ n" S
    排序对于每个开发者来讲,都多多少少知道几个经典的排序算法,比如我们之前以动画形式分享的冒泡排序,也包括今天要分享的插入排序。还有一些其他经典的排序,小鹿整理的共有十种是面试常问到的,冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。
    & p+ r+ X: W) M' b7 E9 ~* I
    - W  i4 e6 ]) E. m% b* ^8 d9 m虽然我们基本知道了这些排序算法,但是在实际项目开发以及面试中往往出乎我们所料。在面试中,经常会被问到各种排序之间的比较;在实际项目中,往往排序的数据不是我们所练习的整数。
      e0 }; W% i: a8 W3 [9 d
    5 m2 E; m3 m* u, z那么今天我们来学习一下,插入排序比我们之前讲的冒泡排序有什么区别呢?面试官问我们,我们如何回答完整呢?
    ! @$ n% v1 E1 c0 t; e3 K- @$ i1 O: {$ @1 k' q* D4 q. M
    思维导图; @+ F/ a: Y. @# I! v6 s

    5 T- O4 S% }2 M$ `2 C3 `) {8 d/ Q
      w6 k4 A( q& c/ i1 N7 J/ i# w# t) T" T. q: U

    : V5 \, n1 |( D1 M" x0 A1
    9 q: q+ ~- T% X( s8 \
    ; S& c6 @  J6 m! ~如何分析一个排序算法?. D: Q' M6 P+ E
    . B3 C+ P4 b! ~/ ?5 ~4 m
    之前写的一篇很详细的文章。
    8 l1 B# k& @  [$ n; w
    9 {' j- U/ m; q9 N# o5 u佩奇学编程 | 复杂度分析原来这么简单8 K& x$ V2 J: A7 B  c6 |

    1 B7 C6 G5 Q4 t9 D$ n' t7 D分析排序算法已经成为我们衡量一个算法优良的重要标准,从以下三个方面入手。& S2 a; ~) a; D" r

    % @2 v4 o0 e6 q# A1.1 时间效率" o5 N* a0 W! T0 H

    ; B, j( u/ L0 S9 V7 d5 D这里所谓的实践效率就是时间复杂度,相信大家对于时间复杂度并不陌生。
    ' ]; T5 L/ Q- o! Y# b2 v. }2 o) l
    0 f! O" Y+ y5 u' k4 z# `复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。2 X, G. a" o" {7 R; h: `) ^4 F" u
    ( p3 \4 o% Z. S: M, s
    对于时间复杂度的分析,要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来,分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。: h; M# z* g- l. H, m6 d" _

    9 E/ a6 f0 b' N5 b$ t: I2 l1.2 空间消耗5 D8 Y: S% p: l/ N
    + ^$ B, Z9 T4 i
    所谓的空间消耗对应的是空间复杂度,在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1),此时该排序叫做原地排序。
    0 H# t+ Y0 R$ ~3 s' @4 x* V) x& r3 |6 n% ~, X+ S! B5 k/ j
    注意:是额外的内存空间,存储排序数据消耗的空间不计。' X* ]; z/ r; o( J6 D

    $ U/ w4 S& P) z; F* q4 L, @) R) s! J1.3 稳定性
    % h& f) z" G+ c+ }" V
    4 p- G+ V" J# @8 u; ]% c7 c算法的稳定性虽然我们之前接触的很少,但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢?比如有一组有重复待排序的数据,排序前后,重复的数据顺序不变,此时该排序为稳定排序。否则,叫做不稳定排序。它在实际应用中非常重要的,今天我们就不多说,以后会慢慢分享到。- t$ d! ^: t6 O+ B
    + r# @  s3 a; r- X
    2
    1 o. s+ @7 V+ N  }! x! }0 `' K  M
    什么是插入排序?
    & t* Y2 b4 h; N* z$ F) t4 w6 s. P: _6 A2 C4 a6 L
    顾名思义,插入排序就是通过插入的方式来排序呗,最经典的就是打斗地主,可以将打乱的扑克牌作为未排序区间,手中已经排好序的作为排序区间。每次我们摸牌的过程,就是从未排序区间,通过插入的方式,插入到已排序区间。那么这个过程就称为插入排序。; O6 v1 [# U: C9 V- v" U9 m8 z/ F

    % [! @5 ^/ \% W" x5 g. B9 i. M  ?6 u" X, }
    ( ]0 a$ s7 b' @/ K" t
    3
    1 m6 V; H. V3 M0 I8 Q8 G& U+ P' `
    如何实现插入排序?
    ( Z! f% ]/ b' n, b( i& k2 e8 |, s1 z! ]8 l" C* x7 W
    上述插入排序的概念我们已经理解了,那么给你一组数据,如何来进行插入排序呢?
    1 o( t- |# x5 J$ R' s/ U9 j& r- B% X! s7 T+ O% H

    ( p# M! p3 w, o* L2 W0 U: c3 s- R% i  Z
    & t8 N! ?4 e9 n+ d首先我们要将数据划分为两个区间,已排序区间和未排序区间。
    7 y7 k( P! [# O  o- M# d& o  f4 m8 {6 v7 s
    4 C: V9 [4 I; S- H! A

      @5 \! o: G* a% J: Z9 Z
    5 S6 v% c; Q; b  R0 }3 U, ^/ [2 s' [
    # |, c2 y, u2 y1 g我们从未排序区间取出数据和已排序区间的数据进行比较,如果小于已排序区间的数据,那我们就交换数据。5 i2 k9 G$ C  l; U3 [; O' \8 R
    # Q4 Q0 N" z; G" F1 e3 p/ k
    8 X% V3 ~0 @& _# d/ q: k. p( R

    2 B% L; e. E2 H& H8 L( X! r3 a' X$ [2 N: e) a* F
    ' z' w* V' I+ q; U' D1 j# i
    如果交换到已排序区间数据不在大于插入的数据,然后将元素插入进去。& t/ h0 H9 M5 P! M  [- n, d

    3 Z9 C$ m) d+ p7 }" E2 Y# |  U4 S3 F; I% X: C  k: L- u9 F& _4 w

    & `5 l! n; R+ X% n# s9 a' O; q( J& B0 j2 c9 s3 B
    : l# A& M' `9 B( A/ F4 V7 |; `
    最后我们看一下总的插入排序动画和代码实现。
    : k! q/ S; U- P
    , V* y$ V0 u: u8 }: t
    # L4 l" l9 O* ]  g7 v& d
    - K0 v$ ^% K* \# v# R4
    : f2 @/ b4 G0 T8 k* Y$ N: {
    / B" R+ r7 ^1 x0 ?4 G插入排序的性能
    . t* u+ l/ H1 S2 o6 }8 q! U2 K5 g7 Y9 {3 u* x% V6 r
    我们通过上边的对插入排序的拆分讲解和动画以及代码实现,想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够,我们在实际项目中,还要考虑插入排序的性能怎么样?因为才能更好的选择适当排序应用到项目中去。
    7 p1 b1 K# A; V9 e) m9 r6 r7 B# N0 H) m3 ]# ]" W" `( a1 T* v
    4.1 插入排序的稳定性
    5 ?) ?" L- Z8 S5 f2 n% U# S- c; ]+ l: |4 B9 e) o2 J' p! z5 h' }
    再插入排序中,如果存在重复数据的话,前边的元素再插入的过程永远在第二个重复数据的前边,所以插入排序后的重复数据前后顺序不变,所以插入排序是稳定排序算法。
    3 s1 b" r6 L% B1 h4 C" p
    * {) h: z# n# a) x. \) G4.2 插入排序的空间消耗
    % s8 h! P1 b6 p) ^+ T9 ^
    % C# J. b. A& m; i* k我们可以发现,插入排序的移动方式,需要消耗常量级的额外内存空间存储,也就是代码中的 temp,所以时间复杂度为 O(1),我们上边讲到,空间复杂度为O(1)的是原地排序算法。
    3 ]- @# X/ A6 T: f6 H
    0 V/ m% o) T* x6 ~4 o9 ~1 Q2 a( A4.3 插入排序的时间效率
    ) l% P: `/ w8 X3 Q* i! u
    , p% `9 }! @, s, k3 |插入排序的最好情况就是不需要搬移任何数据,从头到尾寻找插入数据,每次只比较一次即可,即一组有序数据,所以最好时间复杂度为O(n)。! t4 D5 S' A; ]" Q9 L# a; x

    $ p7 p% C5 V% ^$ ^# B如果一组数据正好是倒序输出,那么每次都需要比较移动所有数据,每次移动时 n,n 个数据时间复杂度为O(n2)。3 [" g0 v1 O: Y( t8 F, Q, x, _

    ! ^# j; w' x3 R3 H1 u+ {) Z& G+ e1 F对于插入排序的平均时间复杂度,每次插入都要移动数据,插入 n 次,所以平均时间复杂度为 O(n2)。
    . U6 `, s9 W* [- A9 X
    + {3 I  `9 d- U+ l2 [4 M  K59 A# l# g7 j: x8 r% T; D# k

    $ h) k  z  w, n1 I5 O/ S4 R" T8 m小结$ Y) f8 y: B$ O* p8 e8 o
    ) n- _- p# n( C
    我们学完了今天的插入排序之后,我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢?
    ( Z% P7 G# C' S3 Q* D5 t/ V' @1 r  l+ y- I# V0 |
    我们现在元素移动次数上进行分析,如果一组无序的数据通过冒泡排序排好序之后,它的交换次数是这种数据的逆序度;对于插入排序来说也是一样的,移动次数上都是原本数据的逆序度。
    5 }' s3 A% [  ?- m& l' S, A( C% p; y# F# ?7 S
    元素的移动次数是相同的,那我们接下来看看元素的交换次数。从代码上分析可以明显看出,冒泡排序的一次交换需要三行代码,而插入排序的交换却需要一行,所以总的交换次数冒泡排序大于插入排序。9 e1 l( d) ?- F$ N* k+ p7 {

    ' W6 a  L5 N0 o4 L/ ^  e有小伙伴会问,这两行的差别有那么大吗?移动一次,我们可以不计较,如果数据很多,想想下,两者的效率差别很轻易的就比较出来了。. s4 |/ ~- Q" ]' ]* j" @/ k

    , g" L. [2 p1 n! x! {/ ~4 t& ?! ^7 d虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的,但是我们实际使用中还是优先选择插入排序。
    6 ]4 Q$ j" ^4 N; i! K- D# M7 H
    2 T4 m! o2 H: E; D4 @. ]6 n7 L5 B对于插入排序还是可以优化的,对了,没错,就是希尔排序,我们在这不多分开写,后期会继续更新。
    * o/ p' U' c! u5 R+ b- V————————————————
    ( K. q% c4 E7 w+ A8 B1 T版权声明:本文为CSDN博主「胡鹏程的博客」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    ' f! ^; U2 `. J+ K! ?' e原文链接:https://blog.csdn.net/lyshark_lyshark/article/details/126792708% v* T8 b; m8 J
    6 ^9 n& n% Y2 N+ Y- R( A7 @* E

    : x3 }) p, l0 b+ {+ k; F
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-15 03:09 , Processed in 0.348070 second(s), 51 queries .

    回顶部