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

2744557306

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

$ E  E3 K* `7 t& R! ]" }以下是一些常见的排序算法：

, R4 f  Q/ D5 N7 v& y" r冒泡排序（Bubble Sort）
! M4 l/ }* O! |; t( [
9 e/ Q" w7 I7 o) e4 B- O3 [插入排序（Insertion Sort）

选择排序（Selection Sort）
$ \0 y2 n% {2 }# C6 Z
归并排序（Merge Sort）

快速排序（Quick Sort）

堆排序（Heap Sort）

一、基本介绍介绍
7 [/ w' Q2 ?. H7 P1.1 原理介绍
* y: x* C* `( r( j归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
# p1 K5 g/ C! [5 B7 [: C5 s1 E* `
0 S$ y9 n8 G2 i- c2 k( d2 {: p! _归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
4 Y3 j, Z4 X( S# {6 j) N  z& A
& v6 U* e% P- }9 ]. I/ ?; m分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
$ l- d8 F+ ^; a& P0 G6 _* g
  {9 {; S: x# [: [4 \. j定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

8 ]# Z. N) L4 x6 S比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
4 c' ^0 E: M" c
重复步骤 2，直到其中一个数组的元素全部放入 C 中。
( Z0 U2 _( o9 p0 i. T4 w+ R
将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

原理简单示例
% [# @  T6 U5 Z% H7 W$ C以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
% S: z6 n" N3 D; z: ]- D: u
( \( M2 f% X+ t+ U1 M# F接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

1.2 复杂度
% ]7 ^! u2 b/ {5 S1 `归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

/ u; k# d2 v; `这个复杂度可以通过分治的思想来解释。
$ m/ q' d: J. |4 U1 R+ E
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
5 |5 x& D2 P3 O9 l7 o2 N
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
/ I3 c  u6 C0 y6 J. W. [
- r  T8 a) a# v/ \) }5 {归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

7 Q0 f) r0 b, o这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
: N9 R+ s5 B9 K) b- \+ o
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

! U8 ^6 [2 d% @对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
3 r1 {+ |5 D  A
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

. _4 A6 n9 @. T! _对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
9 @1 n7 X" u# L; h7 n* Z
2 z0 k* s7 E  _/ ^4 M对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
6 i0 [- ~# n; f' p; i- R
5 Z; n0 v$ i* D" W- M! e总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

6 j& C# |% D1 F5 Y6 w二、代码实现
: W: m5 ^4 n' J) `; s2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):; R  S1 Z\" u- q: F! n0 @
   
2.     if len(arr) <= 1:
   5 C; H7 M9 U+ J% C& D! a\" I8 `
3.         return arr
   ! N/ ?7 W# l4 b$ r\" Z- D
4. 3 k5 h2 I# E7 R0 Z8 H
   
5.     # 将数组分成两个部分  u3 n$ h5 d- j6 H1 P& v
   
6.     mid = len(arr) // 2' e9 u1 ]  v2 G
   
7.     left_half = arr[:mid]
   8 Z' z1 e- U5 L- h( S  {* i' q
8.     right_half = arr[mid:]+ x6 B. N- _8 f$ m7 J
   
9. 
   ! f8 O& `2 k! h. [
10.     # 对左右两部分分别递归调用归并排序
    $ i6 @1 |4 ~* S2 p  L
11.     left_half = merge_sort(left_half)
    \" E$ N: m9 v+ g; H
12.     right_half = merge_sort(right_half)
    8 [0 I: k; f1 l% ?. e# u9 q
13. 
    % D1 F0 z8 B2 |/ K4 }+ E2 o
14.     # 合并左右两部分
    1 c3 S1 O, i+ v0 M# j& I) Q: \( B
15.     return merge(left_half, right_half): J0 o\" v* q% N
    
16. , ]8 u! `  F0 q8 o) j! m; D3 _% Y
    
17. def merge(left_half, right_half):
    ) B  K% O! s. a; i) g/ `\" x9 g( l
18.     i = j = 0
    ' d  i( }6 B! J/ j1 B; `' K
19.     merged = []% R. ]* b' L8 c6 F
    
20. 
    ( S9 J/ f7 n7 n- v4 ?/ L
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中# ?\" J/ j; \! l2 m- f
    
22.     while i < len(left_half) and j < len(right_half):
    1 r, I9 _: ?( c0 J. G* }; y2 r( t. f
23.         if left_half[i] < right_half[j]:
    1 z; z7 T+ Q, g& |
24.             merged.append(left_half[i])
    - O+ `; |  e' I+ m
25.             i += 1, i! S; X. a4 \4 \$ J; t
    
26.         else:3 @$ M\" W  P* }+ {6 r. r
    
27.             merged.append(right_half[j])
    ' q! F2 m# H- p
28.             j += 1
    . @' R, ~5 [8 w2 {; j
29. 
    / ~\" n0 t$ a: u1 V' Y! j: o  S* c
30.     # 将左右两部分中剩余的元素添加到 merged 中3 x$ h/ a8 w! X) e) U\" i
    
31.     merged += left_half[i:]( N7 Y1 ^6 v7 _\" P. \
    
32.     merged += right_half[j:]5 e1 W8 R, X\" T! ^  u8 N
    
33. * j& W- \% k* A/ Z$ u
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   ( G4 F( l% `& o0 v5 D# P  g7 i
2.     if len(arr) <= 1:
   - q% b1 U5 l; w& c( c+ x% ]
3.         return arr
   * z/ }! h: J% N7 X# {/ E& ?
4. $ r& `/ }. W+ r) O% \6 o
   
5.     # 将数组分成两个部分+ k$ U' g2 S/ L/ ~8 m
   
6.     mid = len(arr) // 28 h$ D: i$ J# A4 r
   
7.     left_half = arr[:mid]
   / B0 G0 U% p+ g& ^( l- D6 v
8.     right_half = arr[mid:]2 B% g% {+ }# p; x- j/ r. k1 l- A/ L/ r
   
9. 
   0 Z$ Y2 h% C\" n  Q
10.     # 对左右两部分分别递归调用归并排序$ n& I3 b6 P& m& z' e4 g3 L2 C
    
11.     left_half = merge_sort(left_half)' R4 d( N0 j: |0 i% n
    
12.     right_half = merge_sort(right_half)\" \* _. W3 k. L
    
13. : g) L. b  W; I: B% M4 \, {
    
14.     # 合并左右两部分) G6 C& ?  \& A* J$ U
    
15.     return merge(left_half, right_half)
    7 l7 C+ e9 T; ^8 S
16. ```
    - M* t! n/ B5 ?9 c1 ~: d- z
17. 6 m8 J0 p3 m% J9 L) Z& I, b
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    + y\" V& ~8 X7 E

复制代码

merge() 函数

1. def merge(left_half, right_half):7 w\" v& b6 ]7 I\" X2 K, @* a
   
2.     i = j = 0
   0 d) q$ a! a% n4 Q
3.     merged = []
   / K- Y: N3 k* ^! T! z  q* L
4. 0 o5 {/ s7 E6 {\" t  W% b6 E9 E
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中1 @- b9 W9 O! Q! A2 n
   
6.     while i < len(left_half) and j < len(right_half):
   / [\" i$ h* H( W: H
7.         if left_half[i] < right_half[j]:
   0 o, `5 f. `$ G) F
8.             merged.append(left_half[i])$ k) _, t! x6 Y0 F) V/ ?( x
   
9.             i += 12 P. ^5 ^/ K# L, ]
   
10.         else:
    ' {# Y' G# t1 D# ^: t, E+ Q- j
11.             merged.append(right_half[j])
    * Q& C+ K/ Z$ V$ o# G6 h! M
12.             j += 1: G$ W' d' F0 v3 t1 F, u. i
    
13.   U# [, D# M\" d
    
14.     # 将左右两部分中剩余的元素添加到 merged 中' v9 _* Y. U2 ?; N1 z
    
15.     merged += left_half[i:]
    9 Z\" D( B1 O* s: F
16.     merged += right_half[j:]
    * X0 @3 _' A  |! x) n% @) {
17. & b, G, [, J0 g, e
    
18.     return merged
    9 @/ i: p6 j; I$ E2 @6 J) C! u
19. ```
    5 q' _; w' c, v' Y  S# _
20. 3 [( s* y$ {0 m* ]9 S2 D- i/ a
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

5 s2 {( C- y* n  |* o! d判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

# x" K% @+ |. g对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
- y3 f! g5 o, F3 m8 x
测试
  P6 h) J6 S* I3 M在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   % M7 a5 V# s3 R$ b2 [
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。

总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
4 e8 H! f3 c8 y+ R2.2Java实现

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

1. public class MergeSort {
   # d2 G8 t) I6 ~! N
2.     public static void main(String[] args) {
   5 j2 l\" {3 d1 J0 E\" _
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};0 y, ^+ k  |. t+ ^; V' b6 l# g
   
4.         mergeSort(arr, 0, arr.length - 1);\" m. I+ y. k7 n( ~! }6 a
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   9 B/ q5 j\" O' }- _$ B; `1 h  v
6.     }& M/ J1 V; ], H! o. j* a2 g' a
   
7. 
   ! S9 }! H( \6 J2 S0 B9 y$ G+ t! f
8.     public static void mergeSort(int[] arr, int left, int right) {
   - i# t' y  b' j6 I; l\" U
9.         if (left >= right) {
   * d0 K$ F9 Y9 l3 F& I\" Z# f\" [
10.             return;
    + o: X) \5 ]- p9 ^4 L
11.         }
    9 _: g  X. [2 L0 n; D0 h0 k% K
12. 4 i0 q* N8 g9 f8 M1 F
    
13.         int mid = (left + right) / 2;
    6 h\" v6 y3 |3 O. a
14.         mergeSort(arr, left, mid);
    % k% |1 @& {8 O
15.         mergeSort(arr, mid + 1, right);' y4 \; I/ f8 q
    
16.         merge(arr, left, mid, right);  V( \! x; Q: p) }
    
17.     }/ Z: z- G$ x. ~, C# r$ G* \( o- K
    
18. : i. U5 K; {/ b7 V  B- b1 ?
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    : o2 I+ W7 e$ r: `/ f
20.         int[] temp = new int[right - left + 1];2 V8 k& w\" ^3 N
    
21.         int i = left, j = mid + 1, k = 0;
    9 [- Y  |: ]) N7 M
22. 
    : e/ Z\" P. U0 ^. P9 [, G5 L
23.         while (i <= mid && j <= right) {3 c& }) m* A( w4 _
    
24.             if (arr[i] < arr[j]) {\" P# Z# A' H. x0 Q
    
25.                 temp[k++] = arr[i++];. w& T: u$ {9 H; j) v7 u7 r8 F
    
26.             } else {. A\" w9 P5 b- L, r8 B4 [0 ~
    
27.                 temp[k++] = arr[j++];; u% y: b' q: r5 e9 W$ v% y; G( S
    
28.             }
    ) v! q) M4 y, ]& d/ d
29.         }4 e6 s5 w3 u7 x+ c( O4 f! p
    
30. ; @. T# s  B\" [+ ?
    
31.         while (i <= mid) {# P9 H# x7 H+ X
    
32.             temp[k++] = arr[i++];- ~& o: B, w4 J) a( k8 @. E/ f; ?
    
33.         }0 M- ~8 ?% h5 \& ?. L% k0 I* K4 x
    
34. 
    4 c3 W* D: c$ Y1 `  u, a+ ^7 G
35.         while (j <= right) {
    ! u% x3 t7 W$ a$ j* x
36.             temp[k++] = arr[j++];
    - u+ R9 |% ?; R$ @# w3 v' d\" q+ K
37.         }7 p! j! J$ \: k3 U% \
    
38. 
    * f! N( w( p+ _0 A$ \! Q3 i7 J
39.         for (int m = 0; m < temp.length; m++) {7 T$ v* K3 H$ V2 ?3 \/ z- [4 V
    
40.             arr[left + m] = temp[m];) x& w9 R) i' t, }# Y& [8 o\" d
    
41.         }3 \5 ]' o- M/ u! O( W# b* V6 ]8 Z( V
    
42.     }1 D  g+ i7 N8 z5 J6 {1 B/ p
    
43. }

复制代码

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

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

" u4 P- w3 Q' l0 C7 w* O6 ]mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   - G; L3 E! E9 Q% y! U, L. O
2.     if (left >= right) {+ h$ N0 D0 T$ {
   
3.         return;- w. ?\" @/ |1 Q: o. j
   
4.     }
   0 M$ U4 Y, k8 z: y
5. 
   - H5 s& Y5 K' ~
6.     int mid = (left + right) / 2;
   * G6 R; H, X7 Q2 o0 {) l
7.     mergeSort(arr, left, mid);
   ! e2 B6 ~; A\" o! M
8.     mergeSort(arr, mid + 1, right);) |: @- b1 S7 K3 ?+ g, u
   
9.     merge(arr, left, mid, right);
   \" }5 C  r4 g$ X
10. }
    $ `8 W! _2 R( u- _
11. # @) d7 |\" h2 t# N2 _
    

复制代码

这个函数使用递归的方式对数组进行排序。
4 Y9 R0 y- J+ P9 i: J4 m9 i* K$ ]
9 x3 y' [6 D9 Z对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

; T: k: d' p9 F3 Z: `最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
/ F# Z& V( ^  }; H& r( `+ Pmerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {/ l2 I2 F9 P* a7 C! ~
   
2.     int[] temp = new int[right - left + 1];
   + c* H- k, ?2 t3 A
3.     int i = left, j = mid + 1, k = 0;
   + b/ W- m7 J  }- S8 K6 t8 ]6 ^
4. # y3 w( M% n0 F0 e5 l/ u\" z: M
   
5.     while (i <= mid && j <= right) {
     R! S: f; X- h2 u* _8 n  _
6.         if (arr[i] < arr[j]) {
   . I# R2 v\" e! T6 \6 ~0 R+ U
7.             temp[k++] = arr[i++];  Z9 o+ R! \, G+ T
   
8.         } else {
   & c/ e\" i\" O2 C: x0 c1 w) ^
9.             temp[k++] = arr[j++];
   ! _: x1 n: x+ h1 x
10.         }# Y1 k0 R6 ^/ h' ]# \$ F
    
11.     }
    % u: V8 O! U) _) U& Y4 q
12. 
      Q1 d! Z( ?- \+ ?. o
13.     while (i <= mid) {
    5 M& m* F6 D4 z  c( k4 i3 o
14.         temp[k++] = arr[i++];
    , T3 U) S% s\" m9 k& `3 t8 M
15.     }
    $ ]* Q) ?9 {$ G- Q4 a! m0 k
16. 
    . y9 x9 D  c0 x) V4 A
17.     while (j <= right) {
    8 a5 U# R7 a) q- [! o7 {3 v1 I+ D. E( H
18.         temp[k++] = arr[j++];
    ( ~! S' L6 K0 ]9 c
19.     }
    / f$ T3 Y+ X0 ~! A- E) E. Z# ~
20. 
      j\" L( }5 c\" f) B
21.     for (int m = 0; m < temp.length; m++) {
    . v* _& @; J) `0 `  J
22.         arr[left + m] = temp[m];  @6 F7 N; K) X5 g: l\" |; w/ C
    
23.     }8 h\" I* }! P6 b8 l  \9 q( k7 P
    
24. }
    / f- ~1 |) H( U& \7 Q) \7 r

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
& K- w  V7 c4 p8 Y
4 o1 d' L. B- D* x, u合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
5 \/ c: L" l9 p; [6 _
2 O4 h  F$ K1 A5 z( w0 l$ i+ Y最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
- i% B8 M4 w4 ]* p: Q7 c! a
+ o  g8 u2 w8 s1 u* t& S这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
+ x6 T- ?, t! w/ K1 I




4 l: [# e. c- w
9 ]! u7 F" L0 H' t# K, R6 N
7 a8 H( ^: i2 p; J4 W