QQ登录

只需要一步,快速开始

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

[其他资源] 【基于C的排序算法】插入排序之直接插入排序

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

5273

主题

82

听众

17万

积分

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

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

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

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2022-9-14 16:31 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    【基于C的排序算法】插入排序之直接插入排序
    " b, q! ?+ q2 M& p5 x: t. t1 X# |5 ]1 _& j
    前言
    / c+ g6 L; v1 p5 h0 r本文基于C语言来分享一波笔者对于排序算法的插入排序中的直接插入排序的学习心得与经验,由于水平有限,纰漏难免,欢迎指正交流。
    - _! _2 C* D9 n/ N* N# P, k
    2 D( k1 N" P+ [, u/ Q直接插入排序0 e- D1 n& C% g1 k2 w6 Q
    ​ 直接插入排序是一种简单的插入排序法,其基本思想是 :9 F' |# w1 a/ K0 h) \, \. s. O

    9 w* C6 E% l$ `3 }" T​ 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为8 e: A6 F1 o$ [1 h1 I' V4 ^
    止,得到一个新的有序序列 。
    9 x. Y0 n* h4 }9 ?* k) z​ 实际中我们玩扑克牌时,就用了插入排序的思想
    . [6 ], l' b2 W1 w& x6 |/ Z. r+ z
    1 w) e$ N- k' f( J! N, t' z) T5 P  z6 G3 m
    8 ?+ Z7 Z9 F. X/ }$ N: W2 C
    ​ 当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array的排序码与* Z5 t+ U% o" W# n9 n( ^
    array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array插入,原来位置上的元素顺序后移。9 y; y, g- t, a( g" p

    * ~5 W+ _  r, L2 w  z& F升序排列的示例:( X# p" r( x, M3 P% f: J
    * M& s: z( ?! O

    , m+ y4 @) L" r0 s: R& ?  i8 ?" V. }$ A, R) {
    下面以升序排列为例讲解过程:. M8 b: o5 Z0 ]! [4 H7 l

    2 H6 g5 P1 Z! K​ 原序列中可以分成两个序列,前面的是已排序的有序序列,用一个下标end标志该序列的尾,初始状态下end是0;后面的是还未排序的序列,用一个tmp变量暂存未排序序列首个元素,实际上是通过tmp = arr[end + 1] 实现的,也就是end指向的下一个元素。为什么要用变量暂存end的下一个元素呢?因为有可能涉及到元素后移,比如说,如果arr[end]要比tmp的值大,根据升序,应该把arr[end]的值后移对吧,那要是直接后移就会覆盖掉arr[end + 1],所以在移动前要先把元素暂存到tmp中。在每一次比较后end要递减一下,向前移动。要是tmp比arr[end]要大该怎么操作呢?这时候就说明找到要插入的位置了,把tmp的值插入到arr[end + 1]即可。7 e' i6 b* l, ?& @- p
    3 m; v: ~5 X# k9 V! x5 F
    8 D! s' a; n. q' d, `
    ' K. E+ F7 C. X* k/ d
    ​ 可以看出,直接插入排序不可能只有一轮,像前面讲的过程就是一轮的过程,结果就是把未排序序列的首元素插入到了已排序序列中并保持原来的顺序,正如把刚摸到的一张牌按顺序插入到你的手牌中。实际上,一开始序列是全部未排序的,我们可以把第一个元素作为已排序元素,也就是说已排序序列一开始只有一个元素,end值就为0,后面的元素就全部都是未排序序列的了。; L) D! I( g1 |: x0 W

    . P: D6 a; g0 [  X! F- k/ }9 H( e; t+ r# s0 _

    ) X8 C8 b. m1 S+ E! |+ g4 h​ 也就是说要将整个原序列排好序的话要让已排序序列拓展至整个原序列,也就是end要不断增加到size - 1(size是数组元素个数),end值为size - 1时结束,所以还要外套一个循环。$ t( R4 Z# `* Q/ [& j! H" ]

    " r; z. h$ Y" F$ u" ~* Yvoid InsertSort(int* arr, int sz)
    / m& I, A# G' w$ Z{0 t) z, d& w4 N( ^  ~! C
            assert(arr);3 r7 x- h' T1 C8 {
    ; e* v8 ~6 |9 I- @
            for (int i = 0; i < sz - 1; ++i)//i的取值就是end的取值,end最多取到sz-2算有效,当它取到sz-1时就该结束循环了
    " ]  F1 ^7 w- x4 s5 t6 l3 S: ^( Z        {
    ; ^" ~+ m2 i0 e% c& o1 H1 J                //单轮排序" t5 d6 j# X9 |6 R. w  B2 S
                    int end = i;5 b; `) C& `1 E! B2 M4 Z
                    int tmp = arr[end + 1];
    # \. L$ B3 ~4 ^& Z1 j% R5 [                while (end >= 0)//为什么要>=0呢?可不可以>0?" F+ V4 G! n" ^- @! Y4 N: U
                    {
    4 B" s! j1 e4 u; j9 q2 h                        //要排升序                ; c& m- z% Z# V* M2 f
                            if (tmp < arr[end])
    4 w5 G4 O' F2 N+ x: h* Z                        {: m& Y3 h, u8 G5 i1 r$ J
                                    arr[end + 1] = arr[end];- I, h) m/ N$ d3 d' n
                                    --end;" S5 ]  i$ S' y8 H
                            }
    & L+ \6 G3 c9 I7 E2 C                        else
    & N6 T' F, Q+ r# w- T! v% q                        {                                5 {6 x2 R6 W# W' s$ s$ [
                                    break;4 S. F' \5 q6 M7 }; K
                            }               
    6 F* b+ z* l8 Q6 G( W+ {9 s9 x                }. c, m1 j7 [: z: Z: ?
                    arr[end + 1] = tmp;
    0 N4 I3 _* L) e4 x  {3 v# L, V        }3 L" ]0 F6 Q& k$ V  q  o. s3 y
    }
    ' A* g8 A  A- ]6 B5 w# k
    1 t% E4 G1 q, s1
    $ e0 t4 j! L# f9 w" a! r3 o$ ^) h2# y3 M1 g  e# o$ a
    3
    1 l! K9 y2 j* w4 {. v; q+ s4
    " d9 L0 _, M) n56 H  v  y1 m! G/ |+ b$ I
    6
    * a4 s# ?0 v. y& m# K7 C6 y7
    * ~# \6 s/ `3 A# m7 s  q8
    % h7 B: @( R! c; N( e/ L0 \9
    : v/ @! x# O* s; t& x/ l101 _# x# {: j( L% i4 c+ D
    115 r0 ^& @9 C3 Y6 y4 N
    12
      H. g6 x. d$ q  v8 l, o13+ T' I1 s  f9 o: Z* g
    145 `! r: {( w7 ^, h+ D
    158 V* B( b1 ]7 N
    169 e: c9 d5 n3 v6 w8 Q# g& d
    17) X# w- t( {4 a- M
    187 g6 J" A! x- h; A) ?6 j4 U. M( D
    19
    2 z, [9 B. u. N: m! d' @, H$ M20( ]- p1 h/ E2 E
    21
    % a2 U7 B4 ]% m8 V6 S8 l% S228 E1 q9 z* A! x9 ~, _0 O
    23* i2 u* z" y! ]# s9 d* J# Y8 S( u' g
    243 T0 v. U' Q2 x; O0 A
    25" O  [2 T2 |7 a. s- k- O
    ​ end可以为0,因为有可能tmp的值比arr[0]还小,那就得让原来的arr[0]后移,把tmp放到arr[0]的位置。' c/ H0 y2 S8 N: T* Z6 O. [$ O4 j

    # V; U$ s7 p7 W0 B5 Y; ]% w& F3 _
    ) N& O1 G, V# n4 D; o" C; t1 T
    ; ?+ V4 H8 q: T* W' d. ?6 X7 ^6 O直接插入排序的特性总结:( w) |5 {' U; W8 c/ ^  b% b

    ! x1 C/ @" A/ H4 c5 n. c元素集合越接近有序,直接插入排序算法的时间效率越高,最好情况下(有序)时间复杂度为O(n)
    7 t' Y3 q4 v4 g! e- ]时间复杂度:O(n2)
    ( u, k3 q: i8 ]/ G空间复杂度:O(1),它是一种稳定的排序算法
    ! q* m) Z! e1 T' k稳定性:稳定1 Q0 i9 v$ d: B. l" C( R
    感谢观看,你的支持就是对我最大的鼓励~
    ) N% e" {+ C+ ^0 S8 ?————————————————8 ^2 ^% Z0 U% T2 i0 \" x$ s
    版权声明:本文为CSDN博主「桦秋静」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。+ l) e1 n3 S9 X. O& K! {( ?
    原文链接:https://blog.csdn.net/weixin_61561736/article/details/126796593
    , x2 [. x$ R3 t6 |; T
    8 y& |1 a; `- \2 o8 l
    * |) [6 o9 _0 H, b" y; @# Z. w
    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-7-9 09:49 , Processed in 0.618301 second(s), 51 queries .

    回顶部