QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3277|回复: 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:22 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    【基于C的排序算法】归并排序/ @+ Z) y6 y5 S) h0 y" z# H  `

    ) ?" {( X$ L. v# r9 `, n0 m前言
      a0 _- Z* r9 U0 g# l本文基于C语言来分享一波笔者对于排序算法的归并排序的学习心得与经验,由于水平有限,纰漏难免,欢迎指正交流。8 S) y% `3 y: w
    9 f' a5 _, |+ U1 |2 F% I
    归并排序& X8 N2 m$ I9 H; H' {
    基本思想
    ( s; G$ @# `5 Z  N8 x​ 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。5 N" m3 H/ C4 F/ U- \
    + w! m0 ]5 k+ Z
    1 B1 n( a/ G; U/ V& Q

    3 w$ L5 \7 W2 r0 w  u​ 合并的思想其实和有道题目的思想如出一辙:, ~! Q1 H7 Z: i( Z! W
    ) |) y# x  E2 m, @/ _* ]

    / k/ k( w8 y: `  D- j' Y' Y; ]7 S" \2 [8 L6 Z
    ​ 我们考虑新开一个数组来放入排序好的值,要不改变顺序的话就要用尾插,让nums1和nums2数组元素的较小值尾插到新数组中,两个数组总会有一个先插完,另一个数组就把剩下的全部尾插接在新数组后面。+ I6 ^0 U/ Y! W5 |+ j2 S, B
    , O4 N3 G8 m* _5 ]. S
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gsgj7Cmx-1662793985599)(https://typora-picture-1313051246.cos.ap-beijing.myqcloud.com/归并原理.gif)]- B8 t5 d7 i* C7 E( V9 M- ~/ Q' t
      w) x  N# G: |2 D8 ^
    int* merge(int* nums1, int m, int* nums2, int n)
    3 I$ E2 v+ s5 S0 M0 \9 R{- B4 d( v6 a5 u3 R" ]) K
            int* arr = (int*)malloc((m + n));
    " |8 e' w6 Y! F5 s" }! _! k" w2 o    if(arr == NULL)
    ( x2 Q0 Z! G1 J$ g& J  @( H8 n    {
    # ~  D+ W' W& G# p- u        perror("malloc fail");
    ' T. K7 o* i! i' E# z        return;4 \1 g3 C7 r; j0 h
        }
    1 S, K; z7 w9 g3 {( \5 w% U$ K- V; _/ G. n1 G" {; n, S8 [  ^
        int p1 = 0;9 D- Y3 `7 g# ^# j; B' p
        int p2 = 0;
    3 c; e, ?2 j8 a    int cnt = 0;
    $ K9 d/ A5 z; [5 v( X    while(p1 < m && p2 < n)
    / x( h4 h+ z0 P( h( |5 {    {8 ^8 o% |6 s6 }/ B
            if(nums1[p1] < nums2[p2])1 [/ a( ~4 b, F, K" y6 f
            {
    $ c8 v/ S* q) B            arr[cnt++] = nums1[p1++];
    ) u( ]3 r! K. P6 ^8 g2 D4 ~        }* C( z& b4 d6 v0 c& U
            else: R* q& c; K: @+ P
            {: K, j) Q. ?3 r- I- O7 M
                arr[cnt++] = nums2[p2++];
    : K! M* ?; L8 c        }  N8 o- a& p6 @5 G. @9 \
        }6 e" `7 ]$ j, y- ]
        while(p1 < m)
    & [% m# a/ v, P$ @+ J. P        arr[cnt++] = nums1[p1++];: h. F# }/ S- x

    1 X8 j/ \8 M& t8 w' l1 r. M7 V    while(p2 < n); G& X) g5 t0 N2 |1 P
            arr[cnt++] = nums2[p2++];
    2 R" u) j$ n! h5 p1 T7 Z5 H9 k
    ) g5 l0 r8 k# K9 s    return arr;
    6 h" H2 _. g7 X}
    % |$ _# W! A/ i
    ) j; `5 \* y; `: Z- K- w  Q; \* Q8 [1 y1
      r4 r' d, o% P2* r; \6 _# J$ k. w
    3
    ' m9 s; i7 G( U4 z4 u- c* f4
    2 {+ _0 D/ i$ t) G5
    / \7 f1 n3 d0 P) r6
      ?6 t3 |: }( }, a70 {% D& m8 D: D: J5 I
    8& N% A4 m0 K8 R, i
    9: Y9 O1 P  u3 ]. a( d2 N7 f7 v
    10) N( y: s( i1 P% G
    11
    ! l! L# Q  \, p7 }5 b127 H1 w5 j2 l7 t5 k6 P2 \' ^
    13' h) }" G' D  f4 Q8 e5 P2 X
    14
      ?: _- w5 J  y. g, ~15
    5 B2 ]0 h3 b! S  h. Y9 f$ V. \: M16
    $ m5 W7 l! d& `, {1 L171 }' e5 Q$ u$ A( N: ]
    18
    3 g' ]* y& ^( K3 M3 p% c19) x( o# B: k# x9 {
    20+ w. ^  q' F$ x# ]0 M/ ]2 |
    21* d5 ^1 T* Y4 K# ~7 N* c
    22
    0 d9 M+ k& _; Z/ P  C& J23
    1 c( ?" v% V' M; o- J6 i0 R24
    1 [& J  y0 u/ O) [" s3 `* [25
      B0 n  R3 C- [  V26
    ! i% s2 t" S$ ^' ]' G6 ?' S27/ W9 {& _$ x2 i% }* A
    28  w( O: p3 e! z3 V" l
    294 y1 N  U; H" S1 @5 R
    30
    " D% {( S( y2 L31( B% n/ T0 B( g
    ​ 所谓的合并就是利用这样尾插的思路,我们就想到要把原数组分解成两个有序子序列来合并,那么如何将原数组分解成有序子序列呢?容易想到用递归,其实非递归(迭代)也能实现,我们接下来具体来看看实现方法。
    - s; T* B% S& r: T2 u" p" P# s* j5 L2 N4 R
    递归实现
    . i8 Y9 B: R9 K. {: |​ 通过二分分割出两个子序列,然后进行递归,先左后右,不断分割直到子序列仅有一个元素时子序列一定有序,这时候就可以往回退了,等到左右子序列都退回后就可以归并了,不过不能直接归并到原数组,因为会覆盖而丢失值,不妨归并到另一个辅助数组,归并后再拷贝回原数组,思想就是前面讲的合并的思想。+ p0 y$ X! C7 ?) {
    6 p- t5 L6 W6 L0 W6 x+ O

    ( F' z4 x: B, H% a, ^- h7 z' @. Y. k- k
    ; ?: y: J) P: r/ j6 y( y. {# F2 G
    ; E6 K, {6 y4 M4 G
    ; H. ]# i$ l1 b6 R* ivoid _MergeSort(int* arr, int* tmp, int left, int right)
    2 Z, N# E  j2 s0 r" X{
    1 X' F. h. [  j; A    assert(arr);
    8 p# g9 C* o9 |: c- R8 f6 e, x5 b$ M$ Z0 \1 _
        if (left >= right)//递归结束条件不要漏了
    , G2 w& j5 i  u+ W- k5 B        return;1 O$ @" h! s# e  C2 I. Y
    ( g0 V$ P, c; R2 Y2 D1 V1 ?, n
        int mid = (right - left) / 2 + left;
    ' O1 E/ Z3 r3 k* I+ |/ }9 ^  W" a3 I6 m
        //划分左右子区间[left, mid]和[mid + 1, right]
    + T6 `5 X* S7 ]% x1 o    _MergeSort(arr, tmp, left, mid);- w7 T9 F! {0 M' }$ ^4 P# {, @
        _MergeSort(arr, tmp, mid + 1, right);
    9 l: J8 f% r  \/ X* d3 u3 q9 c% d
    % d5 K  D5 H6 K# o, ~7 l    //归并( c9 E6 l/ y* o2 L7 V4 ]* v9 d/ l
        int begin1 = left, end1 = mid;1 W: Y% ~( k/ O$ Y6 k" I) Z! m
        int begin2 = mid + 1, end2 = right;, ^& g5 h5 V: X" x% w' |! \
        int i = left;
    8 _/ P  n( q0 V8 `( n    while (begin1 <= end1 && begin2 <= end2)
    - r4 ~7 X0 x4 ^0 j    {" `/ z1 ]2 k! ~1 z
            if (arr[begin1] < arr[begin2])2 Y! q8 M, M5 a0 D) j  X# ?' l
                tmp[i++] = arr[begin1++];0 e8 K% s! K# W
            else
    ; R5 V& K! ]& M8 f: H            tmp[i++] = arr[begin2++];8 K- \4 M) I5 L. q5 _2 H
        }% e) k, p1 F& }8 i+ X
    " Z0 h7 W4 @  G5 w5 P# W, z
        while (begin1 <= end1)( L, b* o$ \- N
            tmp[i++] = arr[begin1++];
    5 r+ R/ L- k0 N& j4 ]- a: X( U' P    while (begin2 <= end2); ~1 ]3 J; s/ p
            tmp[i++] = arr[begin2++];" ^* z9 h( k+ d* I
           
    ) s7 d  n$ M4 K# t/ X2 Y" ^6 `    //拷贝回原数组——归并哪部分就拷贝哪部分回去
    9 o, w* z; I3 }# j- r    //而不是拷贝整个数组回去
    9 B8 o/ C6 Z' d    memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));. ^* I" a# {* x0 a. p: I6 _
    }
    - _. e1 x9 r8 _2 A
    , m, o" {& E1 a* u6 Uvoid MergeSort(int* arr, int left, int right)
    : ]; o+ r  r9 b7 A# h- M{
    7 X, L# G4 Q2 _' m: Y    assert(arr);3 Y6 C. k+ A8 _6 A

    3 k5 r! K7 n& x' p6 V7 T    int* tmp = (int*)malloc((right - left + 1) * sizeof(int));+ A* J7 g2 g$ J  C; l) x( K6 F
        if (tmp == NULL)
    6 z& m  [/ E, L1 D& N& C% N    {
    + R* B5 T1 p' Q% D$ `( Z        perror("malloc fail");
    1 s- g, ?; E; f/ ~- `0 K        return;
    ) s4 e: g6 r7 ?5 K7 ~    }. ^2 s% t+ e% T5 {5 d/ e- o

    4 ^" ?5 I: i2 G- @. o. g. a9 N! d    _MergeSort(arr, tmp, left, right);7 v3 P- q* e3 V$ j7 Q" z* @7 f* O

    : j5 ~' \8 y. g( y3 \    free(tmp);
    7 s( c, T- G+ t" i    tmp = NULL;
    : O2 ~) }! @) J+ N- L) m}8 ^4 k% c" \  ?+ h5 y

    * o7 L/ m2 ^6 j) R8 ]14 M4 J; m2 V- T1 e1 o" ~! w) M
    2
    * C! x& X! X5 w5 Y7 Q3 c1 a3
    ' g, Y0 t' w/ c9 s5 N4
    $ h9 o  I- X+ v) ^6 r( ?! t5; X0 ?5 Y" m1 T0 A6 K) w
    6
    1 ?5 B" k6 t9 X# ?6 Z7! Z. x) A6 H: i0 U
    8
    + X+ X* z3 M2 |8 P9! ^' ~0 U5 t$ X
    10
    ) @8 i# l, }0 I1 A5 F) w/ |11' _# A$ H& W0 k, R: {# X
    12
    . \4 R* @6 v) m5 B13
    , k3 d( u" f; w/ `3 J/ G, Z$ ?, B14
    1 y5 ~, u( P; b15' H( O0 ~; w5 |. {$ b
    16+ }3 d. }- A, z
    177 p! f( S$ G/ n! E2 A3 E
    18
    % Y' v* b  z- J0 M4 H% M199 M: S% G7 X9 u- s$ ?
    20/ n1 J% n: H$ s$ y# r# I
    21
    , g  `, e' b( S& J! N; C$ z( o22
    0 L" V. N$ v/ v23
    ( K. q6 a9 G) {5 E" q+ a3 ~24- d7 }0 L8 N% X- X) y6 x% ~
    25
    ' B0 z( O! z6 M9 K2 y8 M1 p+ U260 o. e! ?+ h2 |5 f# U' Q
    27
    0 \1 Y" f" m7 E) K) W, p3 I28
    ! u  J& e+ d5 e: i/ S299 A7 }" s' [9 D5 N6 A9 J( }
    30
    # x7 X; i0 A$ T" ?4 H' u; n31' p5 d* S+ r: E
    32
      o4 T3 T2 h$ e33
    * I" B1 `# R# `( O( h34
    ( N3 W1 o( T) N; d+ f35/ L/ ]7 \# c& P; g* W
    368 k2 Q8 `4 i. m1 A5 Y
    37: y8 e8 i# J/ B! p5 ^3 u* H
    38
    * z' \8 x+ T% a39
    & @  }8 l- h0 Y1 E; w, I5 J, p7 c* a8 u40  U5 i, z& ?, G0 F  r
    417 C; Q8 c6 ]+ H2 C( S$ D; I9 P
    42
    2 b! |/ I9 ^8 J. O$ b! K# P. C433 u- L" j% P- y* C: O) p- ]
    44# M* R5 F% `5 A" T- e
    45/ W( B+ F3 C  h+ c7 O5 U
    46) C/ b7 ~& w- a4 G1 s
    47
    - g  J8 u! Q3 c' ]1 X$ Z48& c& m2 c. C7 Y. f& T
    49
    + d  e* P- L# C* |2 I2 a6 \50
    ; m; {9 E5 @4 D0 Q" d! w51( ~) u! M3 g2 O' i6 G, A; s" z- g
    非递归实现- m8 `0 X( |/ Q
    ​ 直接在原数组基础上归并,设gap是子区间元素个数,从gap = 1开始,因为仅有一个元素的子区间一定有序。为了方便,我们把gap=1叫做第一层,以此类推。
    : [# V0 @0 n& W  s2 K0 b- G+ A" I7 O

    ( |- `2 F% e% |( w/ ]% V9 p+ V! N8 B9 H% O3 z, G) G* K
    ​ 不同的gap值代表所在层数不同,每一层都是从左到右两组为一对地取对配对归并,i就是每对起始位置,之所以更新i的时候要i += 2 * gap是因为每队两组、每组gap个元素,所以要让i跑到下一对的起始位置的话不就要跳过一整对的空间嘛。" P& q# t! }8 R

    % ~1 E$ z) D) ?% L​ 还要注意区间的取值,每个区间就是一组,就有gap个元素。
    - p: y: x# m8 s* a$ X8 n3 ^
    ; d2 [) H' o* p( n​ 整体拷贝遇到越界就会比较难搞,所以我们这里用部分拷贝的思路,每次归并后直接拷贝,要注意一下指针偏移量不是begin1而是i,因为begin1已经在归并过程中被改变了。
    2 v# o! Q, ~* ?0 ^" |, f7 A! E+ r% D6 P$ O
    代码实现4 \/ D8 {& D. N; U5 S& l8 E
    ( C) v' `( {" t: T" F, {
    void MergeSortNonR(int* arr, int sz); T0 P- ^8 n! F4 H. ~9 A9 Q7 S
    {
    " y9 F8 p% H6 i) N    assert(arr);
    0 n+ R8 K* i& d0 e1 B, G/ \
    3 a* w' n6 u; P1 u/ Z    int* tmp = (int*)malloc(sz * sizeof(int));( f, g  G; w6 J% H. H
        if (tmp == NULL)/ x! M& }9 b7 h4 V
        {- w! ]: i, b6 @; U% y. @
            perror("malloc fail");: h0 o7 p8 j% t% i
            return;
    ! O* G1 O! W) ]6 N! |    }7 u' \$ r0 F( X# o+ b9 v  U
    & O0 w# E0 a+ r; \* H5 G9 f
        int gap = 1;  l3 n1 R: f3 G
        while (gap < sz)8 p: z/ F5 ~2 N  j$ Q% ~
        {
    6 q* O% h: M8 ^0 Q) u" z4 X        for (int i = 0; i < sz; i += 2 * gap)
    3 i- g. U- d4 G        {
      O2 r2 n# p  R0 U0 Q# z' J% u            int begin1 = i, end1 = begin1 + gap - 1;
    . [0 B* f: x$ N, Z- G* p            int begin2 = end1 + 1, end2 = begin2 + gap - 1;
    . {6 Q9 \5 e: l( |" q            int j = begin1;! E' \3 e# ]" {2 _3 }8 ?4 q* d/ o
    6 D0 i. n7 b) s- r; s! k  h
                //归并
      W0 N) L. k. f" }1 @. [            while (begin1 <= end1 && begin2 <= end2)
    6 R4 v- v& u+ F) S% [            {+ H( U3 A  [9 W1 I! ]- D
                    if (arr[begin1] < arr[begin2])
    7 B0 w3 p6 C/ W7 |' T7 N                    tmp[j++] = arr[begin1++];; t8 ^( i3 ?/ H! R# x( q
                    else     + m# p& A/ A' j& y) `1 {
                        tmp[j++] = arr[begin2++];
    # ]5 b; H! Q" P+ J            }2 C& X% ]+ B( j! b/ E6 g

    5 }: Y; V" X4 s! J% c4 A( p            while (begin1 <= end1)" b& c2 a9 |8 R$ `& N4 ]
                    tmp[j++] = arr[begin1++];. W2 v2 F0 p3 a/ L$ i
                while (begin2 <= end2)
    : V4 l  ], ~  |5 j% d& |$ o                tmp[j++] = arr[begin2++];: v" j" U: {0 U& ^
    * p3 X5 c! [% a( ]7 I
                //拷贝回原数组——归并哪部分就拷贝哪部分回去- K: l2 |" x5 A+ @$ ]
                memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
    0 W# x3 R* z& D" g; w        }+ |7 O7 O( P# O' Z% k+ _
            gap *= 2;& t8 ^0 }$ [. I4 Q  o6 T
        }
    7 L" P: g* A' u+ z% g- e' m# `" n$ {- n
    }
    3 ?* n8 e7 b" i- d
    ! P1 `: B* {# {& W9 d1
    7 G, B! `; h8 W  k2 @. @8 }4 e2
    8 p9 o. s& d* G* A" u3; e$ z3 w' |1 C; V6 x* M) h$ Z2 Q
    4) J- b( a) g% d8 L' l, B
    5- w8 h# V! \8 N) V; l! d5 h+ S! G
    66 U. ?1 u+ l2 P" P) t' x
    7! H9 {' x" H; B# k8 {3 n6 l7 E. g
    8
    2 a6 M7 F$ }" C! J7 P99 m, i! T0 a& O
    10
    4 I2 `/ @! |  Y. \/ r4 J11. l5 S- {5 G# q+ y" S3 I; u
    12' a' R' {0 d) k2 c' n
    132 a" Y: q/ K2 ~' A' ^5 s) |
    142 V8 L" g) f, m7 F, k8 Q& _8 l
    150 Q7 z+ z7 N) T+ w+ d% H( u7 o$ U
    16) @$ q; Q2 I, K" e
    178 y  ~$ k9 v0 [# J, \; H3 x! r
    18% K# k, f& L: a6 H& j
    19
    % o& T) m, w# {20+ T1 G6 a7 E" I
    21* n2 f0 @+ I- w+ S( z
    22
    1 D) ~5 m1 g" d23# h5 _( x2 E( |& h; u$ [
    24
    & g& q9 [) J# L  r: g/ K25
    / U7 ~6 e; C9 @4 j! T26; `! Z0 ]& d' Q0 c: ~9 P
    27
    2 ]1 }& r8 r# Z7 Q* ^( ^, c; o# j285 y5 H/ Z, W$ e( Y
    29; W# R! x0 h* i7 I8 a3 k
    30
    5 k/ j1 A% D0 _* r9 S31
    8 U$ k) F2 ^5 Y7 G$ A32
    # s$ r- [3 n' S6 t333 n$ a' V  H. `: ~: Z! ]$ x
    342 S- G, c: P6 V" A: U- S
    350 e: P/ [$ W, B  a6 ^5 Y
    36
    9 S3 v6 U( }+ S$ C/ n( I37
    5 u% ]- W9 O2 A38
    3 `/ V% D8 P# E39
    + u8 n! W. m5 [8 J) ?* p401 ~% i# A: g8 X$ r* {* S+ p
    41: `) _/ w6 Q9 @- q
    边界问题
    : ^" \/ z. C' Y4 K. h​ 实际上还需考虑是否越界的问题,上面那段代码并没有考虑,所以还需一些改进。为什么会存在越界的可能呢?因为我们是以gap的整数倍去取区间来归并的,而区间个数不一定总能满足两两配对。  O- ^3 C! t# U" w

    5 T4 I& m" D+ H2 H4 G8 {. Z! K举个例子,就把前面的那个数组后面加上个元素5,没有越界检测时出现的情况:. j  N* ]& p7 E

    2 d' C" A! {/ d" W! A. Y( i, L' ~  W$ y

    # ?  n) J7 c3 l由上图可知越界分为三类(这里将[begin1, end1]、[begin2, end2]分别作为第一和第二组)5 d& E, A8 l* p5 D( P: }

    $ H6 \: N/ z, w; O, R第一组越界(即end1越界)0 i2 s/ {7 S7 _2 G, B
    ; k8 A0 h4 W% h# Z
    应对方法:这种情况一般介于第一层和最后一层之间,break跳出for循环,不让越界值被访问。; d5 N7 h* W: U; K

    9 X/ Q' U! k8 [1 h/ e; m第二组全部越界(即begin2和end2越界)
    ; ^6 O9 R/ [# r$ y2 i4 @( L- ^- G: t6 F$ U6 z! B
    应对方法:这种情况一般在第一层,break跳出for循环,不让越界值被访问。* `0 O% z9 F, _) R# i+ N

    $ ^; y. f! K: a' ?第二组部分越界(即end2越界)
    & Y) ~" N( [6 }# u3 t* Z; L1 W) a: j* X0 N
    应对方法:实际上这时候就到了最后一层了,把end2修正为sz - 1,不跳出for循环而继续归并。3 O% }# N- j0 w( [$ k
    / {1 O* m  L) X2 {% w
    ​ 其实第一种情况和第二种情况可以合并为一种情况,原因:
    * ~1 R* n$ I# g5 ?8 a7 D- C; j, i* c+ Y$ G2 `5 w
    ​ end1越界时begin2和end2由于比end1大,它们两个肯定也越界了,也就是说发生第一组越界时满足end1、begin2和end2都越界,即包括了第二组越界的条件,这两种情况都满足判断条件begin2 >= sz && end2 >= sz,同时第一和第二种情况的操作都一样——break跳出for循环,所以可以合并为只判断第二组是否全部越界。
    ' D$ d' R; I6 M2 E" q$ b
    ' g/ U! y( K* S: M​ 拿两个数组试一下:
    9 q7 P4 U; d! U7 Z* N* o9 S0 g' W+ ?3 o  h
    6 T1 g5 ^/ J3 U1 j7 G
    ; r/ v5 K( A9 c5 r6 B- t: n
    0 X. t2 A, M% W2 ~& }# l. C3 U. o
    2 Q; p% o. P1 C2 u' Q5 \, r
    代码实现
    . k# q& y% E7 `# v4 W$ v
    4 F7 r- G" e1 H3 ~6 {- z; _  G8 yvoid MergeSortNonR(int* arr, int sz)( y/ t( O4 z6 k' O9 u$ v1 K1 T
    {
    ; M0 ~+ p. p- P( N# v* F  ^$ h    assert(arr);
    8 Q) R1 G! }% z0 t8 E, S0 o
    ( Z% i" p( |; A, T) C    int* tmp = (int*)malloc(sz * sizeof(int));
    . R9 m0 X% b% X    if (tmp == NULL)4 B. Z$ l% O* ^
        {
    0 Z# {. {8 j$ L        perror("malloc fail");* \9 C. [" i7 M$ T6 P: D" f, \/ D+ O3 V
            return;5 u' S- f" {9 D( q6 Z6 i! {
        }- M: h) n. W! R! u
    7 {. z' j- t* O2 c4 `
        int gap = 1;
    ' N6 W) c, Q" N8 ~4 b5 t    while (gap < sz)" Z- ?0 `- t0 S7 G; r" s7 l
        {
    ) B5 ]7 B0 L: J! p& C* G6 E: F* x        for (int i = 0; i < sz; i += 2 * gap)
    4 u# B; m* j" M3 G: |- ]        {$ M  E- [0 [" N
                int begin1 = i, end1 = begin1 + gap - 1;8 f8 N, E% J9 ?, J+ ?. G- G
                int begin2 = end1 + 1, end2 = begin2 + gap - 1;( {# [6 f" X- ]; D' `, S
                int j = begin1;( P: {; t7 B' a; x$ S1 l4 X
                            //越界检测
    5 ]; v/ R& L) [! }' g            if (begin2 >= sz && end2 >= sz)
    ' ~" n& W" a# p6 I  B. [# m                break;
    1 p  X! h  u4 E+ t6 w0 ^! O            if (end2 >= sz)6 ?; w5 h3 i2 e  R% k" ~4 }
                    end2 = sz - 1;
    7 F  e! y1 U  x7 J            //归并1 `  p2 a8 n4 ]; {5 J
                while (begin1 <= end1 && begin2 <= end2)/ `" a% G: F" Q3 \! V" K
                {
    3 {2 \, K9 w8 o% [$ l6 v' }                if (arr[begin1] < arr[begin2])
    4 \# r% G- d, M; y                    tmp[j++] = arr[begin1++];7 C8 ]8 e9 z* d9 Q) c
                    else     5 C7 E( f9 {6 _( S
                        tmp[j++] = arr[begin2++];& @  I  S; M0 x8 |0 }0 P1 ?  [+ f
                }# @* a  n+ p7 H9 v: B) _
    7 V/ H4 r1 S8 T; @2 d1 q6 `0 \" d
                while (begin1 <= end1)
    ' |5 Z. e6 w3 v4 ^' [/ |) `                tmp[j++] = arr[begin1++];
    - v0 q, J, R/ x: f            while (begin2 <= end2)$ W  H1 k* j: V
                    tmp[j++] = arr[begin2++];
    # F& t3 Y7 k/ f. Y$ v. R6 W4 C/ v! K
    5 T( d( z, `8 f& d            //拷贝回原数组——归并哪部分就拷贝哪部分回去7 d6 V+ X" M, M6 E6 z. W
                memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));
    $ m9 x' U" _; x) I  i        }" M! ]8 \* y4 e! f0 O& X+ o
            gap *= 2;
    , q" K7 w3 J9 i. o9 J, d: @4 [    }7 e- x1 p" r9 V; D$ A- [1 F' X
    . H! ~5 e0 X, k' h) U( V
    }
    8 n( w% P4 r  k
    - P; M. H0 o- K( ]& m. V5 }9 V1: ]( v+ O( J' H8 M
    2
    " Y; Z8 y* O1 F( s! P; x/ S! H. T, S; i3
    * n4 \0 ?) }! s4  G# Q* U! I8 ]" h, b
    5- Y3 L& A3 Z* R9 d5 W( n+ \  U
    6
    $ B8 P$ l; u5 }7- P. o0 f! G3 y1 G$ m
    8/ S: ^) y9 N" v( H5 W
    9
    * ]( M+ V$ Z+ e& c7 x% A10$ O# h" n* C6 Q1 {
    11; B& |) x, R: ~, A* P& H) ?
    12; ?8 K9 L+ k" p  u' O* o
    13, ~6 u4 z9 _1 B' F5 W
    14. N9 i6 m! Y' a+ X" Y' Q' i/ T
    151 h; j' K/ b% G7 j& L  h) K. H8 z
    165 C. A0 h  l: B& }- _  v9 e$ ?, T9 D
    17
    3 T4 t1 P! Z' ^# ]18/ }% P- u' }% ~  @! X4 Z% y
    191 j# v5 _- T, D& S1 }; \' o0 _& o
    209 y  |  Z( v1 c5 k7 X
    214 E' f' H: [( d6 F/ C
    22
    $ b* M4 ^) N. o+ l( j. O23$ F) }& B! n1 Y6 j
    24
    " g3 \& a" X1 t7 H$ U: K8 _25
    5 U( Y* \% K% ^- r' i) P, O$ Z* K, Z26# F/ C: i/ q5 F6 }
    27
    + [' l. J9 r; a1 Y0 x  F# B284 w" _: b9 J  X( `" L
    29
    / i4 D- s, c" H/ P( y: V30# h# f6 u8 T! L2 S$ j& \
    31
    & E/ e+ l9 D- p4 O( @323 u  n8 J$ J: e/ a2 ~
    331 Q) I6 u& i6 t0 W4 H+ F* h
    34$ l/ I% r, ]: z4 d$ c3 t, r
    35+ ~9 r. O& O3 ^. U
    36- Z$ ]' Y  M5 N* B3 m; g
    37
    & O+ y! {: l* s/ G) S38
    4 g7 c" n4 `5 ?* h) v0 [39( E! E7 n5 E; J7 h! F# ?
    40
    7 K6 R: [* v" Q( N41, P! Q+ I# F8 u' y3 n5 P
    421 z. ^# O9 P3 K5 m$ v2 Y
    438 @3 U/ s* T5 k* i7 W; f
    44- g+ }) N; M( h0 Y3 Z
    45
    . I& I: [4 x/ T5 y7 a! A/ F8 E归并排序的特性总结:
    + g- o) u" x+ K$ f# n! R3 \# R
    8 J9 [( L7 _4 V5 K8 M0 b( ]8 g归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
    & \6 h) C/ n1 j7 a$ q$ F" |9 z- C时间复杂度:O(N*logN)
    ' k5 X* j# ?/ V空间复杂度:O(N)
      i0 f1 s8 }; g. o3 V8 z稳定性:稳定1 d& u2 V9 k1 ~5 H6 m
    6 [% {. h+ V6 n3 e; U& u. m7 v
    ————————————————
    + z+ F. S+ W$ p5 p0 }版权声明:本文为CSDN博主「桦秋静」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    * r% q2 \5 S/ \) K8 n& p原文链接:https://blog.csdn.net/weixin_61561736/article/details/126796657- \, Z+ X$ }. P. l* B+ ]- f! R
    $ u/ P  ~# q3 h+ u# o, o
    ; d! I5 K$ q/ W$ K, a: R* B6 {
    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-4-21 05:10 , Processed in 0.420294 second(s), 51 queries .

    回顶部