深入解析排序算法之——归并排序

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

3 b. K8 `! I/ b' n9 e以下是一些常见的排序算法：

7 W' g$ f- t. B. w冒泡排序（Bubble Sort）
  `2 A/ ^8 \" i
插入排序（Insertion Sort）
5 b  Z2 y% g. T, S
选择排序（Selection Sort）

归并排序（Merge Sort）
3 ^0 V( S1 U1 b1 L7 h( v
快速排序（Quick Sort）
6 d4 {1 m+ ?3 V. p
堆排序（Heap Sort）

一、基本介绍介绍
2 L. d  B4 z" I! X' `2 }% r+ ?1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

" o0 @6 z9 R8 ?$ u# ~' m归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
# v' o; s* W+ V& q2 U4 n
! b5 e# e& T$ _) V0 q+ P; C分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
& f* ^, j# D0 N$ h3 H- y' ^6 V% B
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
: H) s) ~) S  v4 p
1 V: J4 A( o- K  D; l合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
7 N% w2 A, J: F/ A! |
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
5 \; j9 e0 L* [& ^6 B9 n# x, F  {
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
( s1 ~, `& k$ W/ `; Q# o4 b9 y
重复步骤 2，直到其中一个数组的元素全部放入 C 中。

& j3 \8 q( }: H, a) z+ W( g将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
) R0 k% t$ U. e8 @! l
原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
. c& @* u+ i+ x5 B, y
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
& W  G& A! A1 l: t/ Y
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
8 J. L! A+ c; w1 ?
1 a0 \$ v% a1 U+ \  @) K对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

5 q7 I0 a, s' H5 Y. O1 b接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
4 {9 S. _  Q; o$ T" U' [
6 ^7 M* O1 \+ i将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 i 指向其起始位置，即 0；对于右半部分，指针 j 指向其起始位置，即 0。比较左右两部分的元素大小，发现左半部分的第一个元素 5 大于右半部分的第一个元素 1，因此将 1 添加到新的数组 sorted_arr 中，并将右半部分的指针 j 向后移动一位。此时，sorted_arr 的内容为 [1]。接着比较左半部分的第二个元素 2 和右半部分的第一个元素 3，发现左半部分的元素较小，因此将 2 添加到 sorted_arr 中，并将左半部分的指针 i 向后移动一位。此时，sorted_arr 的内容为 [1, 2]。接着继续比较左右两部分的元素大小，将它们依次添加到 sorted_arr 中。最终得到排好序的数组 [1, 2, 3, 5, 6]。
0 X3 g: q+ ^9 Y  w4 q: M
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

1.2 复杂度
  i  i# s1 _8 W9 q归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
0 C1 O' `9 B& v" H
这个复杂度可以通过分治的思想来解释。
0 P$ f8 B' }! V: O  Z
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
1 x+ f2 v9 v% i' X& a
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
/ B3 S! e, ^. X4 k3 R  ^; P. _* Z  }
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
5 ~) {1 a4 w$ C8 S# `. k
这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

. r# L/ v9 @5 C* U. M对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

; o) w6 ~. O% p7 N+ Q对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
  S5 h$ w9 z, }3 e9 {  Z2 t7 J
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
7 g5 v: A- D5 _
1 q: s& K8 E& l- A总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
& _5 ~# F: s% b9 e
' x5 ]5 ]5 e& q6 }7 B; z二、代码实现
" Y! k# z9 l# v7 g" M9 I0 e, A) \2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):0 x/ H$ ^. W% h\" i# C% M: `. l) n
   
2.     if len(arr) <= 1:
   \" _& `4 N( J  Q2 d  m
3.         return arr
   1 ]: \# q( I3 A
4. 
   \" R! C2 C$ O; i3 ?& d& M8 }2 O  x
5.     # 将数组分成两个部分
   : e% Z3 B; [; L4 m- V, t% a
6.     mid = len(arr) // 20 g3 \9 {8 _; Q+ B7 f0 B
   
7.     left_half = arr[:mid]0 b\" V6 B% i8 i9 N
   
8.     right_half = arr[mid:]; N: c' G5 @1 j# _: T
   
9. 5 u( V3 h7 f) z
   
10.     # 对左右两部分分别递归调用归并排序$ l& x9 t) d3 E, L
    
11.     left_half = merge_sort(left_half)
    & R\" v  S& K2 h: x; m( [3 i& y
12.     right_half = merge_sort(right_half)
    \" M\" C: Y! s9 R9 {2 h; Q
13. 
    0 R$ g! X. G1 k8 E0 j: ?' J- x% k
14.     # 合并左右两部分, G/ [- `8 `5 I( X
    
15.     return merge(left_half, right_half)\" {& N) B5 \9 p/ X' r
    
16. % Q\" G. U  e( E) R' p/ e7 s* J  V
    
17. def merge(left_half, right_half):; @4 B# Q' h1 {' z* B9 ]
    
18.     i = j = 0
    . X2 p& K  I- S' Y7 e1 [8 C. S: o
19.     merged = []
    1 O. l) E2 V' P- ^- l\" X
20. 
    $ c' g3 t; g* r/ ~, |
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中  k& a5 h; s' k! m
    
22.     while i < len(left_half) and j < len(right_half):
    $ X2 T+ g5 x5 U4 J4 D8 ^: {
23.         if left_half[i] < right_half[j]:
    3 L8 T# B9 _3 N
24.             merged.append(left_half[i])& k% G. Y$ }  ]+ l
    
25.             i += 1, X) a4 Q! f9 G5 Q. W6 Y0 W- W: H3 b
    
26.         else:
    # S/ ~; q- D, \, N( ]; {/ r; B: p
27.             merged.append(right_half[j])
    & _) M9 L' t* j8 u- e  ?/ x% Q
28.             j += 1
    4 ]8 g3 I3 D/ t: K
29. 
    0 x! h3 Z$ I% l
30.     # 将左右两部分中剩余的元素添加到 merged 中
    * ]% Y4 [: f8 D9 s+ ?- p# l
31.     merged += left_half[i:]
    ' [- z) b, a! t3 S
32.     merged += right_half[j:]
    * V\" j7 j0 s( U5 K: g\" D  k% k
33. 
    2 S. r. B- u. p4 i1 P% s) J\" Z
34.     return merged

复制代码

代码讲解

这个实现使用了两个函数，一个是 merge_sort() 函数，用于进行递归调用，另一个是 merge() 函数，用于合并两个有序数组。下面对这两个函数进行详细讲解：

merge_sort() 函数

1. def merge_sort(arr):
     O' b* Z5 j( ~( i: c  _
2.     if len(arr) <= 1:
   1 H& @2 a6 e7 @9 ]$ G\" n
3.         return arr
   , d- v% W0 H4 I) c1 y+ ~
4. ( ?/ {1 i$ T, A! {- O9 _9 O; q
   
5.     # 将数组分成两个部分% @( [5 C. T, q; p; g
   
6.     mid = len(arr) // 29 \: J# t* K7 m. f5 ?
   
7.     left_half = arr[:mid]) F4 [$ M2 ~7 P6 n# F
   
8.     right_half = arr[mid:]
   # P7 p# @: }! |% }) i
9. 
   9 g; r2 `. Y* _- L6 ~7 q* H
10.     # 对左右两部分分别递归调用归并排序) a+ |* @+ i7 m, Z  B
    
11.     left_half = merge_sort(left_half)  K( p$ t9 A; a6 E1 r/ S5 H+ H7 V5 x; c
    
12.     right_half = merge_sort(right_half)
    9 W0 h9 o' T: ]7 I- O9 ^' q
13. - p2 b1 i7 d) e5 K+ d\" I1 r/ I5 o
    
14.     # 合并左右两部分( d8 U3 O+ R) Q  q- N7 y
    
15.     return merge(left_half, right_half)
    0 s( W. V& @4 o! \% T4 g
16. ```
    ! t/ U( J. m) I9 b% Q\" N
17. . Z# x# S# P8 z6 U0 m
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。5 d7 @& ?! L/ p& D0 o
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   * U; g! B! J3 V( s
2.     i = j = 0' ]- B0 z7 D* h
   
3.     merged = []
   ' P0 g/ e, `, |' ^6 s
4. 0 H$ G6 D# c7 z8 }9 D
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   ' X5 H( K+ K2 e) ~8 l
6.     while i < len(left_half) and j < len(right_half):) G( Y2 ?! b5 W/ u' p) m
   
7.         if left_half[i] < right_half[j]:! ^8 F: I+ @5 }( K; S7 o8 L
   
8.             merged.append(left_half[i])
     T* r4 o& w6 B
9.             i += 1
   ( k1 T7 G' h! v% L, j
10.         else:5 \  d) u' P2 J3 ~! m+ }\" s
    
11.             merged.append(right_half[j])
    9 ]4 {$ |% @1 ~4 d
12.             j += 1
    / m9 A; ^) i$ Z5 `
13. 
    8 O# y% j) b$ L/ A' N4 ^
14.     # 将左右两部分中剩余的元素添加到 merged 中
    ) ]0 B) ?  E) \& l
15.     merged += left_half[i:]
    6 {9 d: y  V$ ^: s/ D0 @
16.     merged += right_half[j:]; q* N6 r3 o\" L* w
    
17. 
    6 |2 d8 a8 t# i
18.     return merged
    2 n3 V' K0 t- r0 i4 T- K
19. ```5 [6 \% i5 N/ r9 D9 b
    
20. . x, Y7 o, N  M. k! R1 n9 U) Q
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
. W6 T( S; \5 w. ]6 G
. ~( N( v2 b' J2 z, ~8 F对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
3 U, X5 U9 `, }
; F7 q* H* ~2 D$ g, W合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
& b0 @8 p) }( o* \( e$ M
9 v( U/ z5 P: n) c测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]  P7 y+ Z& d. _* b8 q2 @
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
  _' ?+ a: p& _3 ]: r* d3 ^) q
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
* k! [" o) o8 P5 m, k2.2Java实现

以下是使用 Java 实现归并排序的代码：

1. public class MergeSort {
   # D6 d/ k# q7 _, h  @% J
2.     public static void main(String[] args) {& F+ I( @/ M% I# h% Z1 Z
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};1 T' b/ k: e- D3 M& }# [
   
4.         mergeSort(arr, 0, arr.length - 1);) y4 w, p8 n\" q! ?4 v
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]! k9 S8 [3 Y6 @
   
6.     }' U8 n3 r5 A6 W6 r  x
   
7. 
   % u( h# }6 W# {6 i8 u
8.     public static void mergeSort(int[] arr, int left, int right) {
   , A6 Y2 c9 r# d9 \8 |. S- w
9.         if (left >= right) {/ F5 w0 s, S+ t' c\" q; W
   
10.             return;3 Q& z, |+ q6 c! t
    
11.         }
    ) z- a: r& C# Y; ~
12. 
    : K  ^0 z& b6 b* Q8 m/ j
13.         int mid = (left + right) / 2;
    0 `: t* I2 m% r$ W
14.         mergeSort(arr, left, mid);
    - ]8 ~% i9 R) j/ i
15.         mergeSort(arr, mid + 1, right);
    6 r, D& J; o$ ], w4 g& P% K. B
16.         merge(arr, left, mid, right);
    6 R, b' C2 p$ q: f. I9 ]$ S0 `# j
17.     }' u, l8 T9 |7 ?) I; p2 N* E, I
    
18. ' L! P$ u4 k  R7 z' w
    
19.     public static void merge(int[] arr, int left, int mid, int right) {8 ?\" x! r+ P. J& P( G. s8 p
    
20.         int[] temp = new int[right - left + 1];$ c9 N0 L\" _' z* [
    
21.         int i = left, j = mid + 1, k = 0;
    8 G' h  ?7 J# x* j, H+ g3 X- ]
22. 0 Q6 v) G- R( k# S3 D. {3 z
    
23.         while (i <= mid && j <= right) {2 W. d' ~  Q3 d' H9 [8 u
    
24.             if (arr[i] < arr[j]) {* S% `# x$ M* l0 B
    
25.                 temp[k++] = arr[i++];
    2 b# J+ B8 a6 P/ q! ~6 F
26.             } else {
    - ~6 b# P; S5 d: s( d
27.                 temp[k++] = arr[j++];
    ) V4 g% S  c6 E\" h) O) A\" [: W
28.             }
    ( I- V4 |+ I2 i2 F% S- q
29.         }
    2 N# O) H, g6 A' w
30. 
    # j/ j: E  z2 y7 }3 O% I3 l- X
31.         while (i <= mid) {
    + q- r! L% R% r( [8 }! K# I
32.             temp[k++] = arr[i++];: H& l2 y\" h# f
    
33.         }
    1 L\" [, x4 z7 d1 l/ K5 q
34. 
    $ \! M6 ~8 }0 x9 a( Z1 W
35.         while (j <= right) {8 G# u: [- @) i* T) e3 M
    
36.             temp[k++] = arr[j++];* ~+ T: {) m* V( y0 S( c
    
37.         }, [: u4 k0 T1 T$ O- m' O0 }
    
38. 
    3 B5 Z& l1 P5 D, z\" h+ q( `
39.         for (int m = 0; m < temp.length; m++) {
    3 h& w' I4 M3 A; [! w( ^+ p
40.             arr[left + m] = temp[m];* |; h* w$ Y8 o  D
    
41.         }; I* E+ N4 g8 B- y: S\" E0 q
    
42.     }
    1 v+ m+ A  M; ]- b2 c  v
43. }

复制代码

这个实现也使用了两个函数，一个是 mergeSort() 函数，用于进行递归调用，另一个是 merge() 函数，用于合并两个有序数组。

下面对这两个函数进行详细讲解：

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {8 u0 K3 y0 V6 f* P\" T
   
2.     if (left >= right) {# S6 [+ T9 @/ B\" C( a2 v3 }( a+ }
   
3.         return;( [( [3 p# h- T\" I5 U% a9 |
   
4.     }2 s6 q\" Y2 b  m3 ]' P
   
5. 5 s; U6 k9 s8 g, v% K
   
6.     int mid = (left + right) / 2;7 i. s+ M! Y8 L/ O* z/ q
   
7.     mergeSort(arr, left, mid);5 }, p- g1 T4 Z
   
8.     mergeSort(arr, mid + 1, right);) W& s# c( y/ l( h. D9 q( R
   
9.     merge(arr, left, mid, right);; ]: l1 }8 \4 H# E) P
   
10. }: j: J' J( g* r2 v2 b+ d; Z
    
11. / @( U0 B! F. [
    

复制代码

这个函数使用递归的方式对数组进行排序。
! e: X% D" k8 y5 K! R' O" D) e
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
' T7 p. y3 f! |( |" I
( p( i3 Z9 ]$ C最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
! M9 M, t& h- V9 `merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {. p& l1 s2 w% u! A- H! K
   
2.     int[] temp = new int[right - left + 1];, c! C  v8 o6 x# L0 G3 X4 k
   
3.     int i = left, j = mid + 1, k = 0;
   : r/ X; a8 d* Y2 E( e( }\" X
4. * O2 Z! a1 s( ~1 u, I
   
5.     while (i <= mid && j <= right) {* K# M! O9 Y  L/ R( E6 R, {7 w$ n
   
6.         if (arr[i] < arr[j]) {
   $ Y/ b+ y4 V! c
7.             temp[k++] = arr[i++];; u2 X* H0 P( w  S
   
8.         } else {
   2 a2 ?0 ~& H: C: m0 |, [7 r- Z9 t
9.             temp[k++] = arr[j++];
   ) b( Z) |6 _\" R. D! k
10.         }
    ! _. {. f5 Z# s# m* y% q, ]5 C
11.     }
    # F! N6 O/ e, [' c
12. 
    . s6 Y7 f, J. K  Q
13.     while (i <= mid) {
    ! ?2 R9 X, j1 V3 W- h
14.         temp[k++] = arr[i++];5 P2 V6 _9 p3 N
    
15.     }
    : u7 A. D0 b- A9 b$ M; t, T2 a
16. 7 x# [# g9 T( X& k
    
17.     while (j <= right) {9 v. N0 [3 ~0 b! P) C8 K: B
    
18.         temp[k++] = arr[j++];# u6 j- C6 f5 {9 X& V
    
19.     }
    7 p. q/ [6 Z) `: _# g
20. \" t1 ~& A: T! X
    
21.     for (int m = 0; m < temp.length; m++) {6 k& Y5 D/ b3 k2 O
    
22.         arr[left + m] = temp[m];4 J: {  d. W; n2 W
    
23.     }2 Y7 J\" l/ _6 A$ u( z! \& t
    
24. }
    ) I/ ?\" Q: `1 A

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
/ A& t4 k( _7 F& I+ j- j
* h: T$ o1 ?4 {. d2 B合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
3 x. L' G; w6 g
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
4 `7 V1 L& {0 h0 Y4 ]/ Q  P$ ^% a- ]
! ?) i& \/ H, T2 Z: I" L3 X; I这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。



9 Y) V% f+ V6 }  ]- u; u9 w$ {: Z
, P* d3 z- j+ s5 b0 T7 F; ^
3 U: |( M+ Z1 Q; H
7 `' b, ^- Y; g3 Q% U' [