数学建模社区-数学中国

标题: 【基于C的排序算法】归并排序 [打印本页]

作者: 杨利霞    时间: 2022-9-14 16:22
标题: 【基于C的排序算法】归并排序
【基于C的排序算法】归并排序
! l: i! z, \+ _+ U3 V+ V( |; I& H
前言
, d6 g0 X9 ~6 D. V7 D+ L本文基于C语言来分享一波笔者对于排序算法的归并排序的学习心得与经验,由于水平有限,纰漏难免,欢迎指正交流。
: s! [8 j( F) P$ W
& ?# j" H* g# M4 ~& h  L归并排序  Z8 T8 o0 N! g: U
基本思想$ l- V& ?' g5 i( s
​ 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。7 Q( @5 U* j" L! r% A  ~

6 D0 Q5 {$ D7 m9 U9 `
; ~7 u% d( F8 ]% c% {# s- H" Z) `0 O. M4 G3 T# ]
​ 合并的思想其实和有道题目的思想如出一辙:( d- R8 E- K' A

3 R( U4 ?' k( r0 u" [8 z0 b& h6 N; R& N1 H( t7 n1 _

- I. _' X% }+ U0 x7 C6 V​ 我们考虑新开一个数组来放入排序好的值,要不改变顺序的话就要用尾插,让nums1和nums2数组元素的较小值尾插到新数组中,两个数组总会有一个先插完,另一个数组就把剩下的全部尾插接在新数组后面。+ q. j) @$ `6 a7 e: i

' a* x) d( o* u- I3 C- e[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gsgj7Cmx-1662793985599)(https://typora-picture-1313051246.cos.ap-beijing.myqcloud.com/归并原理.gif)]* B* ^1 _* p1 @  S0 @
& E+ ?! o0 m5 p" ], b1 s
int* merge(int* nums1, int m, int* nums2, int n)5 Y6 Y. Y3 J. `9 z# F
{
  W1 E; |9 S' z7 O. P# U        int* arr = (int*)malloc((m + n));7 t. P/ w0 y8 @7 Y2 k
    if(arr == NULL)7 c1 w1 g9 _; n3 M8 R: U
    {
* T" f2 L! u: ?" F- k; @# r/ Q+ k1 w        perror("malloc fail");: K2 ?4 {+ M, [& A3 v# f
        return;; N0 @2 M6 \& G( e8 n
    }) c8 M+ I# M6 I# ?3 e6 B0 K6 {
  I+ c, S( P  p% z/ Q
    int p1 = 0;
+ Z9 ~0 h# x' n' `    int p2 = 0;2 L' ]6 L( i0 e" p0 x! q7 E# z+ E
    int cnt = 0;: X5 `: K1 k1 I/ Z$ A
    while(p1 < m && p2 < n)3 k4 G% ]7 |' h" o- c) h; y$ C% k% {- q
    {
1 W* ]( ^7 S. G- d        if(nums1[p1] < nums2[p2])
: |! [8 a4 Z1 x. L. l- A0 ~$ b* {# e        {3 @& s7 r* d- {
            arr[cnt++] = nums1[p1++];
. C7 ~7 C) L; N' g        }. E$ i" _; L; p! K: D( V
        else% G/ [5 ?2 c* _3 A* n
        {
1 Z, d0 Q; J8 u1 ~            arr[cnt++] = nums2[p2++];
2 b4 V- t  i9 @% M- X/ l3 I        }
1 X, b' f8 K: x/ O5 b1 {& p( S    }5 `7 E) M; o/ {3 ?5 l! Y; z: s
    while(p1 < m)2 B; m8 o$ z$ Y6 H
        arr[cnt++] = nums1[p1++];, {+ m2 |6 I7 J' y) l
3 U7 S- V8 I6 o$ w$ K* o
    while(p2 < n)- U7 @' B" a6 X9 d6 w7 j
        arr[cnt++] = nums2[p2++];
% z% Y& t+ K2 F% b5 V( U1 R, \" ^4 `( U$ s
    return arr;
3 l$ a* X1 f+ S% w" G; s% T}
" T: z( g: E, G. g$ Y3 G
: l1 P' s1 J. k1 p* U1
! e- Y  ~4 J. E2 L9 f# ]1 g4 ]  t2
) u: d( W  R/ G, C. u1 b3
% E/ ~3 [9 |1 q* u. k9 ?( k1 q. t4$ I) F1 h+ j5 p6 _
5! D7 Q' N0 S4 L9 b0 `6 d$ Z: g3 s8 u
65 i* _1 d3 z8 f7 d  \3 M& c8 k
79 \3 y" {; p4 t/ a3 @. p
8- j, B, G/ z% W5 m0 v6 E
9
+ h+ Z# z6 e8 f, D7 G7 H10( l$ G1 t1 {! J: N* i1 x
114 Y2 V4 `4 _9 y
122 O' M8 w* f4 V( u) Q5 p
13
/ @6 r+ E3 m/ ^( u0 `$ D$ G/ A14
6 S0 i: h% u, @% ~% B/ U15) H9 o* x' x- B  }  y
16, z3 ?) j% f1 Y1 S* G4 }9 S% X
170 `% o7 q1 E- ~# w3 O8 }
18) \0 m  Y, A; @4 p( b
19
# c, l) }" D  W8 t7 {  m! u6 l20
; w+ S+ _" N* R, g! w3 w21
3 h6 w4 r/ M! x. G# a' u22
: X# I+ D0 a% n) @- }233 M& M6 B/ E$ U" _, S4 h* ^$ `7 j
24+ }: O8 X1 ?( m5 q$ R( k+ i% h2 ?- W
251 n# ~5 @; P! E1 V; D. s& B& ?3 F  x
26
5 J6 ]+ J' [# r, A, p272 o1 M  w5 V2 m  X! W4 ]
28( s# R/ R! ~+ y- h2 T* p8 ?! f
29. g  n9 O  r8 |2 z- l1 O3 d( y
30
8 r4 _/ J# M9 N+ d31
7 x/ j: }6 B  x3 [) n1 Z​ 所谓的合并就是利用这样尾插的思路,我们就想到要把原数组分解成两个有序子序列来合并,那么如何将原数组分解成有序子序列呢?容易想到用递归,其实非递归(迭代)也能实现,我们接下来具体来看看实现方法。6 ?" k4 {( W/ t- D

" Q4 ^& `" Q  k  H( I递归实现/ f/ ^' |. s+ D7 w
​ 通过二分分割出两个子序列,然后进行递归,先左后右,不断分割直到子序列仅有一个元素时子序列一定有序,这时候就可以往回退了,等到左右子序列都退回后就可以归并了,不过不能直接归并到原数组,因为会覆盖而丢失值,不妨归并到另一个辅助数组,归并后再拷贝回原数组,思想就是前面讲的合并的思想。$ F& ]. `, Z9 L$ U) h% r3 l
/ e& Z1 m! T/ ~, t# c$ H

- u$ y% q* z" C: f, C) g4 A
7 ^3 }. I8 f- ^- D2 x) m8 O# O* Y1 u: t7 y

2 @/ N" L+ H4 _" h  K8 ovoid _MergeSort(int* arr, int* tmp, int left, int right)
) I3 v. T+ U# n) F{
: d9 @6 {4 ?  v2 q) v  B5 ?    assert(arr);
( G$ f9 y. v' K8 Y- o* H! P1 m1 D/ O, `3 k) E, r$ C
    if (left >= right)//递归结束条件不要漏了
" o7 l8 n0 _, Z# x8 Q        return;! U# A! ^/ T6 _2 `) K3 |

- Q1 B$ ?, n8 }    int mid = (right - left) / 2 + left;! Z# P% L: u/ e
( W' c5 u9 X* o2 j1 c( z/ k$ N  N
    //划分左右子区间[left, mid]和[mid + 1, right]8 e5 E9 i0 O' o. l7 ]
    _MergeSort(arr, tmp, left, mid);
9 {" P4 u+ @. F* l& V% w2 s    _MergeSort(arr, tmp, mid + 1, right);
  F" R2 e% c1 Z  I0 o7 Z6 b. \4 M9 K& ]6 G% E2 q0 a+ X$ D
    //归并. d3 z7 A0 N5 x+ k5 {  q
    int begin1 = left, end1 = mid;
  h. P$ y/ x5 t; {. _+ S* c    int begin2 = mid + 1, end2 = right;
4 s/ A% k5 X/ d! l) U" i7 q/ e    int i = left;3 Z) p  Z/ r4 @' E1 o: ~: a
    while (begin1 <= end1 && begin2 <= end2)2 |. P) ^) l# `8 ^3 ^0 V, c
    {: i: ?* U6 T  U. H* D+ A
        if (arr[begin1] < arr[begin2])8 Q5 L& }! f. d. L5 n
            tmp[i++] = arr[begin1++];' m$ H& @6 J- ]9 h# s& m4 X; _  z
        else
3 Z  |( Y$ ?5 }- K3 D0 @            tmp[i++] = arr[begin2++];
2 j' K1 ~# f+ i  w; ^    }
1 C) M2 N( M: t7 [3 g3 b; P% \3 G+ y- n* Y* d9 |0 f, }" v/ r
    while (begin1 <= end1): T. y  L+ a1 r  v* a" X# m
        tmp[i++] = arr[begin1++];# z% `# [8 L3 t: v/ y
    while (begin2 <= end2)
  ?2 J  I  c$ [% t  e: N) a6 U        tmp[i++] = arr[begin2++];
9 |" k% I8 j/ l6 c5 k5 p& {5 R       
) W: I$ m+ p3 ]9 S; M+ ?9 J    //拷贝回原数组——归并哪部分就拷贝哪部分回去) g* f# m6 J8 k! G
    //而不是拷贝整个数组回去
( `  N$ C+ z8 c    memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1));
" q: c! @0 ^2 L' |$ ?& O2 s, }}
" B/ p9 g7 N; \/ W/ D& L
3 c$ n; m& f% m0 ~; L4 Hvoid MergeSort(int* arr, int left, int right)
# a5 s7 ?. K3 j! F$ V  G. _{# E8 b$ v7 P% b) u) b$ J/ s1 L, W* I
    assert(arr);5 P2 r. w7 |( Y' u7 E1 y* c+ x
4 N; W0 ]5 X3 `
    int* tmp = (int*)malloc((right - left + 1) * sizeof(int));
* V9 U# }4 ]. {" m    if (tmp == NULL)% G. \  R, ?. F. @
    {
- O/ ^2 M1 h9 ]' ]7 @        perror("malloc fail");  u- u! n; n- u& Y7 y
        return;
- w' K6 |4 U  h, P. ?- ]! N5 q$ E5 k    }
0 w  Q: q3 t" ^$ z3 {  N. m8 |2 g
4 ^+ G: |8 ?# Y4 A) ~    _MergeSort(arr, tmp, left, right);
  z2 I7 E+ G2 K. W
3 B& K% G& A6 [  \6 M    free(tmp);
5 S- x, u! u4 Z5 b- c7 S8 a/ G+ ?: y    tmp = NULL;8 e1 j5 i5 z6 a, C( B7 v5 R- ?
}
# H% j6 g3 v0 g7 p1 I1 u# B" t% z$ P: p; J2 x' `
15 f* N" K* i& s) z
2
; `4 {3 x8 a5 |  A7 K( q: S9 F3' t$ _; s8 e7 @" Y' J' z" o) r
4
* P  k. P! }- z4 r4 E5% P3 U. c" t0 N7 f6 `* o
67 u: z2 e# t6 j: O
7- O1 D9 v$ t" b6 f' @1 ^
8
, n9 D9 S, s% z, g8 [/ I) t% F2 f7 r9; ~; f! z5 B" c& k& s. {. @2 {/ ~
10
6 B4 ~+ ]' C; d* V7 L$ U11+ I4 o$ e7 U: I$ h& O" }; U
12
  U6 J5 N. s2 B/ N( a13
. T( y- d; b# J/ k14! G/ c" k3 O. L* {6 ?3 c2 W
15
. _6 `1 _9 c: z: Z' S/ d+ z6 O16
$ |  P4 Q  G& Y6 a+ J: k  W7 y17+ P) L0 n) ?/ t0 W+ i
18
& Z! i( i7 `; c9 L$ M' l2 M19
$ c5 \5 [3 l# ~8 F# C% [# x20$ X) R8 D, l7 Q& R& A
21
+ J+ @0 P4 j  x# E- f' y221 m+ L2 S+ K& L) Y
23
, e& j/ K+ c( s4 C# t24! n8 U' j1 @" s/ W
25
2 ~; o. p4 R/ J6 F26' L4 M5 U+ R3 M: U# M1 _
27) u9 ~' p1 J4 \! J# r. \" Y/ S
28+ @/ R6 v+ Q2 ?2 d: }9 `9 q# m
29
( g$ x% G5 Z; x" q! c  e30
7 r1 ^1 y4 P9 z" g31
) l% G& m& ?! o32
% i  n3 C$ e  D# j( I8 U. i  I33
) U6 B2 z7 n) E& X$ X8 w341 E. F8 [; g, {# U1 ?
35
+ j7 x! t( s: i' m; l36
. C* v, w* A, l* h37
+ n! i+ }! ^* X38
0 k+ U1 L% I. V# n( f( u" `39
2 j! U1 q! ?3 I  Y' `1 a40
* G. L$ {7 e7 u% X5 u! A41
8 q; F5 i8 h. J9 y42' c) e: ^) t' _
43
, n% h, C) s2 a! @& M/ l* m& R44  t: @1 J5 n9 u
45
; a9 y3 s' t' N( D! }8 P46
; x: `  D( m2 R& o47+ V; _& [! L0 p! ~; W
48- u% H; @1 W3 g4 d5 V; L: u7 f
49
' p/ p4 r; I1 `7 h( n1 `4 [. k50/ \: Z, a3 L! m
51
" X6 ~: [. E, I) w1 ]非递归实现
! o, E  L0 T% B​ 直接在原数组基础上归并,设gap是子区间元素个数,从gap = 1开始,因为仅有一个元素的子区间一定有序。为了方便,我们把gap=1叫做第一层,以此类推。
. h; G. g) B5 e+ l  a6 t* `( U% `! g, W

' M& m2 ^$ i& m
) K6 z3 y. w* T. X, E$ r5 \0 {​ 不同的gap值代表所在层数不同,每一层都是从左到右两组为一对地取对配对归并,i就是每对起始位置,之所以更新i的时候要i += 2 * gap是因为每队两组、每组gap个元素,所以要让i跑到下一对的起始位置的话不就要跳过一整对的空间嘛。( p' M/ K1 H- D  N

4 i- B/ u* t. L) c4 Q# v9 m​ 还要注意区间的取值,每个区间就是一组,就有gap个元素。- e" N. v. @+ ^( z  i- \6 D

, J% s+ X9 b, F​ 整体拷贝遇到越界就会比较难搞,所以我们这里用部分拷贝的思路,每次归并后直接拷贝,要注意一下指针偏移量不是begin1而是i,因为begin1已经在归并过程中被改变了。
6 K/ A; t% _2 d; b; w
: y* y/ C* X, _7 \代码实现4 y1 k2 v; |8 b4 k
8 O8 w: V0 C0 r, J
void MergeSortNonR(int* arr, int sz)/ S2 d0 }1 U* d
{
  j! B8 o% O6 ^4 [! G- ?    assert(arr);
$ \& }/ Q( e. \, H6 I+ U1 \( p7 r
5 L+ {6 k$ r$ R( K    int* tmp = (int*)malloc(sz * sizeof(int));! h1 l: S7 d. r, \7 b
    if (tmp == NULL)
; X8 b+ k5 {+ X    {
& ^- _% N8 \; g) U6 q$ w$ C        perror("malloc fail");
7 C# Q7 a1 G2 y; H        return;
* K# A# b" H0 y  p: u2 T    }& D) X8 |* S4 _, u+ I) H# P
* l3 k6 Q# J3 L! A' {8 P
    int gap = 1;0 p* c& I6 `+ X  s3 C
    while (gap < sz)" m$ p9 U2 M$ l5 P) r
    {8 Z# y& o% G3 {5 h, `
        for (int i = 0; i < sz; i += 2 * gap)
) G0 V3 B2 R. Z) a: ~; G        {* C0 v8 P$ b, d) e
            int begin1 = i, end1 = begin1 + gap - 1;% i2 |& H  z; }
            int begin2 = end1 + 1, end2 = begin2 + gap - 1;3 j* V: K. g/ U
            int j = begin1;& \3 i, ^8 W8 m; W; U
( P4 x4 A; ]( g
            //归并
/ Y' S" Q2 Y: {9 K/ }* t# i# W            while (begin1 <= end1 && begin2 <= end2)
$ J* X* P' S5 M            {+ D& n* ]. s  C% `5 X' x! \
                if (arr[begin1] < arr[begin2])
* @/ }- \1 E1 y& m- T8 q: w( f+ y                    tmp[j++] = arr[begin1++];
$ V4 T: @' d- R1 W6 }5 [3 Z4 Q                else     
7 n! E1 G) S5 B( z                    tmp[j++] = arr[begin2++];
) m8 P" a6 ~5 E: g$ z& p4 p4 B            }
, [# ~4 ], a: C' Y7 e6 ]8 ?/ m+ t6 g& n8 j" A  s
            while (begin1 <= end1)4 p' U' n; \3 A* m
                tmp[j++] = arr[begin1++];
- x! }; s; {. U  N1 m: k- w6 r            while (begin2 <= end2), _3 K" |0 u0 \8 V7 L! D
                tmp[j++] = arr[begin2++];
3 M. ^4 R6 Z+ N+ A7 f# t2 U
+ a0 @) K5 C7 }0 [) k            //拷贝回原数组——归并哪部分就拷贝哪部分回去( W& J! S7 C2 h
            memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));5 h' K8 D7 F4 @  W6 M
        }/ |2 A6 ^9 P  B& G. g0 q
        gap *= 2;
/ Q, _5 c% @, s5 z3 B$ B% @: |" ~    }  c4 Z4 h2 }( b, {5 H- m$ X

( o9 [0 h* V# U}
( s1 H( x# ~9 ?
; t' n$ @; `1 f1
3 B! i4 q5 x- S" t20 a2 M& Y) o7 D. W% F5 a
3% K3 @, B. J9 l8 F4 m
4
1 Z  s9 x3 P" Y( G  E5
. w3 |. c# {  ~6
2 z) u& n4 y2 K* V5 j% _7
& a" L% E5 }& `8/ S7 L" o! b# s2 z' K4 S5 e% j
97 }& K5 \' I8 D4 h
10
/ U) U( Z8 V2 H0 u7 s11' A% ]* }8 W7 P0 R, ~
12
' s; `- d: q6 X9 A* L6 [13
& J, _" o8 b) U$ F* n. ^9 ]14
& u6 Y! }- Z, z+ D( p4 E" O8 x15
  h+ q! \( |0 M% B; @5 b6 T& o- X16
2 {, X0 f; y1 w; h! e6 D17, F" D  z5 K( n3 [. b/ B7 C
18( T7 E) t: e9 w
195 e9 f; h3 O& o- i3 h( n4 }  ~* F1 d
20
# Q( ]0 ]! B0 ]1 G8 @3 k# ^/ W* r21
! c7 m: p4 O3 z5 e% m22
/ a' A+ A3 f# Y% W- T. e/ t& r23
. e5 E5 a  r! E2 a24. X0 ]8 ?' a% Z/ b
25
  M$ u4 i/ ?7 R" p4 h26( e  {; V' A+ ]
27
7 f& {9 @* R% r: h7 }9 o28
; f3 Q% ^: X* t4 s# l- y29
" ~9 b6 q/ }0 l9 ?1 a# i303 [5 L" T/ v! c3 \2 D
31
6 }" M* D! U; }32
& A, F4 l7 u* o3 b$ f( y7 z( d8 `33$ a8 U' Y7 ^. u$ U$ p: D' Y' E
34
5 q1 V. V3 r; ^& \- ~( O35  z; I. q$ @1 o5 F3 ]( {7 ~
36( ?- K  r2 m/ S1 V& A
37
# X2 I( O2 y7 c, Q38
- Z* u  Y1 l* h4 C3 U39
. t. s8 \& |- w6 S& D: ?4 o' ^406 J4 M2 A" ~' L, i9 m% T  R
41
7 p8 L$ T5 M) v1 z0 R  B# f8 Z边界问题. v) o/ {# V8 D& |# X- g! O
​ 实际上还需考虑是否越界的问题,上面那段代码并没有考虑,所以还需一些改进。为什么会存在越界的可能呢?因为我们是以gap的整数倍去取区间来归并的,而区间个数不一定总能满足两两配对。
' `0 d1 g2 D9 M( r0 {3 h6 Z, u
5 ~' d# p% d1 B" Y$ k; h举个例子,就把前面的那个数组后面加上个元素5,没有越界检测时出现的情况:! p( w6 C- \! ^' {3 ?. K

9 h% l( r2 [5 }" }0 e9 P3 Q( }( b1 q1 m

; x) f/ t- d  p# W( |8 U! h) x9 q" R由上图可知越界分为三类(这里将[begin1, end1]、[begin2, end2]分别作为第一和第二组)( A" t% E) r6 Z8 u1 }1 E
4 \7 g0 z) j- b+ U0 ~! ^1 s% g+ g4 [
第一组越界(即end1越界): T/ W4 J* m$ E( e" m1 F
! i7 p* V; \5 A" y2 ?% Y3 \
应对方法:这种情况一般介于第一层和最后一层之间,break跳出for循环,不让越界值被访问。
5 Z& ^; Q5 H+ k6 i9 d, _2 e7 K- L; z7 d( G" R
第二组全部越界(即begin2和end2越界). G5 h% H" A# j: e
2 _/ R$ i6 a0 W% R
应对方法:这种情况一般在第一层,break跳出for循环,不让越界值被访问。- `2 h6 a3 @4 p' Q, N
3 }) K2 H5 b' e* s! J
第二组部分越界(即end2越界)
, E& q' u! [# |
" O4 w1 x" f6 J2 h" J* H应对方法:实际上这时候就到了最后一层了,把end2修正为sz - 1,不跳出for循环而继续归并。" \- t- p; }4 N% |3 O

  i9 E9 [  D% t2 f​ 其实第一种情况和第二种情况可以合并为一种情况,原因:
' I9 O$ ]" B  A) I5 A9 Y! n+ s( @  w# J$ U9 p
​ end1越界时begin2和end2由于比end1大,它们两个肯定也越界了,也就是说发生第一组越界时满足end1、begin2和end2都越界,即包括了第二组越界的条件,这两种情况都满足判断条件begin2 >= sz && end2 >= sz,同时第一和第二种情况的操作都一样——break跳出for循环,所以可以合并为只判断第二组是否全部越界。9 w8 M! G% }8 ]( c7 g2 B

. [& {+ R. Q9 o. c, U! ~  O​ 拿两个数组试一下:# _! t5 j& i1 {: F

$ l- E% O; _  I; ]9 i6 J
" I! {& y4 k- }8 @/ q9 ~) m) @/ k9 _- c" z+ o. F
: @8 X/ r$ L$ {

* U: E! L6 g; g" }- z* C) m代码实现7 J7 H6 c  |+ H' ?, Z/ K1 ]5 V6 |
+ a. ?7 S9 K- r0 p4 ~
void MergeSortNonR(int* arr, int sz)
: o. ]1 X: E. p  D- K! @  ~7 t{
) a- \$ u! b2 V% D    assert(arr);, ~8 c- {4 _# e  p" J3 q
5 L0 e' }6 b. C8 ?9 M$ _4 O% Z
    int* tmp = (int*)malloc(sz * sizeof(int));
' [3 l/ L) C* K1 y# B    if (tmp == NULL)( o& _6 p; {; U7 P; l# I9 d
    {" B; u6 t4 y) P+ ?5 B0 p0 H- C
        perror("malloc fail");
: W* r* m' ~/ {, ~5 `! E        return;& A/ |: k3 }& i/ M" p9 o
    }
1 P. \$ Q0 X$ X; |& ^+ X- k- p& k; B7 X
    int gap = 1;
& w* Q1 p" S5 D$ K) z( M! E' l' b    while (gap < sz)2 |' L* d. ]9 N" `0 o, N' G
    {
& T/ K+ v2 b% l% S+ e        for (int i = 0; i < sz; i += 2 * gap), L" ^/ R$ n9 u* I+ ~$ O
        {, P+ I4 t4 D1 i( |5 z% i1 M
            int begin1 = i, end1 = begin1 + gap - 1;
2 {( i5 A2 z# ]0 `            int begin2 = end1 + 1, end2 = begin2 + gap - 1;
! s5 z/ v' f( I+ M3 `; \4 @            int j = begin1;
/ E4 p  u# z1 H+ z- x                        //越界检测
1 @. k* L2 k7 W# G/ D( d            if (begin2 >= sz && end2 >= sz)8 _+ e1 ~/ I2 m/ Y+ n; F* e
                break;
4 H* E. h. l% P: z% m            if (end2 >= sz)
4 A6 d9 Q: ?6 t" e/ v0 \3 P) }                end2 = sz - 1;, k2 z) _2 j3 e* A9 m1 K
            //归并
8 E% j2 v1 _1 g3 c: `( ?* v            while (begin1 <= end1 && begin2 <= end2)' M5 @' E/ [# S: H$ G( m4 @
            {
9 F. A$ K: A6 Z4 q+ D) q5 V6 e                if (arr[begin1] < arr[begin2])' o' @6 \# F; V" k0 w
                    tmp[j++] = arr[begin1++];0 G, Q& c7 R; I
                else     + t" k+ U& z9 W1 u/ e7 c5 U: z
                    tmp[j++] = arr[begin2++];
& N1 g8 w1 e9 k: V) [            }
) l4 ~, B- k0 x& I) V, ~. m0 e6 ^; W) x# U& k3 N6 s
            while (begin1 <= end1)
; ~( b# Y0 q7 O; P$ W                tmp[j++] = arr[begin1++];$ P+ Y, S# Y, S" Q9 J
            while (begin2 <= end2)
5 [8 }" a4 x6 w1 J9 K; ]7 D                tmp[j++] = arr[begin2++];; h, L/ v7 T. e+ t. U' o

- a1 O- C9 a/ E# z- U" G            //拷贝回原数组——归并哪部分就拷贝哪部分回去+ a; e0 s/ K0 K1 f1 o
            memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));" V& U' I  A- \$ [7 E
        }: W8 Y: J: S% c2 ^' ~
        gap *= 2;  E! Y# U# R7 r2 S- n
    }
  k+ v( M1 \* ^7 t  F5 q5 M: k' U, c; b1 d! h3 U
}  \/ B! a* T- }* h
/ P4 Q6 c) Z+ [: l
1
7 D' ]  y# ]8 O, d& x9 |1 w# L- R26 N* Q- L* K6 g6 D
3+ k$ b' }# M# U$ l. P
44 @. a+ r4 I) U/ H: W7 y9 ]+ u
5  Q4 R% R5 K( G5 e; i
6
' {! n# K" U3 B$ e7
6 t% E2 C! H$ R6 e9 F. O8" h# E" i: D, I! O+ I6 e$ c% _; X
9
, _/ L3 q/ M7 c; {) @0 y10
. u3 A  m' b/ j0 Z) |$ e5 N2 P11
) v* k( E4 e( Q6 R  [5 H0 x* B5 K12
+ K& t! _# G4 n. m/ t13: H7 p4 Y' N* V8 t: ~1 C
14
% |. g8 G' S2 V1 t, E  \% i15, s" i, r; M9 ~/ i& H0 @0 O  D
16; V1 C( V5 X. n" M9 }- J
17' i$ h- N. f% B1 a
18
# p% u9 ]* a/ r  `$ c2 x  L( _/ ~19
* c6 `0 D( o/ D5 @0 f20
& {3 m7 v2 v6 w( w$ T+ g! Q3 N21) W0 U3 M# v4 |9 y
22
% ^8 z8 l1 l. h& B0 S2 V23
/ D' J/ s9 D" x2 K5 t, ]241 k) ^8 z/ a. N$ n% b4 M
25
. i( Z4 t2 H5 a8 T+ b26
& M1 h! ^9 s$ a) T3 w4 f) G27: a- T1 b) p) `+ z) K' R
28
% k$ g& e% D7 M, |( G& Z6 m299 i! p* l3 [) s& _/ t
30
4 t) I$ V' e" b3 Z/ u31
( E' x1 u# _$ Z) F' j. l- D6 b32
& Y. g1 K1 k% L  T33
2 p1 {: E1 I9 L34/ P, y2 F0 y' O
351 D; U% z1 h3 F/ S
36
2 |; S" `* ]6 M0 g$ L37
3 C4 {) H3 F; T& e/ B2 Q( p38: b6 s  i: q6 S- V* n, W
39
6 }; \( }1 t6 {. u  h4 [2 q40
3 X1 H. v1 ^" v* x; A" ^, l41" y& E8 s* j0 [
42
3 O# w* I* D' O+ X# t43
: ?# ~) T- m+ H. \44
. o! Y8 |) L+ w( l" t% {45  J" B5 @9 x: z0 c
归并排序的特性总结:5 m& Y( i0 ]& g* v* t) Y

& V5 w3 C4 {* h* u# A/ U% L4 T归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
: A, W6 a; l4 A7 q, a时间复杂度:O(N*logN)9 L, Z! Z+ S% R0 n
空间复杂度:O(N)
" O0 Q/ K9 [) X2 {9 K) d5 ~( v+ }稳定性:稳定
# L1 S& m7 ^3 u/ a$ l
" E  Z; e5 u* L) B* K————————————————
0 |+ T! ]& y9 q0 e版权声明:本文为CSDN博主「桦秋静」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
9 E2 N& N3 o7 Y$ a/ L+ [2 {  F原文链接:https://blog.csdn.net/weixin_61561736/article/details/126796657
' l1 H9 w' j2 z0 u, L
9 g9 c& A+ b0 |, n3 {, Z6 K& [+ k+ Q- r





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5