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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
  L! e8 ?& u# X7 s+ Z
$ Z! g3 g( }. P以下是一些常见的排序算法：
8 @% H, a! a# {, i0 l  I# S
冒泡排序（Bubble Sort）
4 v1 g& o0 |8 j: C' t+ t
插入排序（Insertion Sort）
& D  _  @; @1 Z9 A; _# H
选择排序（Selection Sort）

归并排序（Merge Sort）

+ Y( F. I6 A; z) j3 U! x2 g2 O8 w快速排序（Quick Sort）
$ I3 N2 ^/ O  B% r7 n: X4 c3 i
1 H  d2 T$ ?; x8 F4 i: R) o堆排序（Heap Sort）

5 v1 [9 W( }* o( N一、基本介绍介绍
1.1 原理介绍
0 C/ _* L0 J- I1 f( I/ F归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

5 F4 p" f8 z7 {; a4 }, V归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
% f" v' M. p' @8 Z& O
0 l( S9 t; s1 ]5 R* M  U合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

+ x: _* S. B4 ]$ R, L: ~5 l比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

  k# {# ^3 J& P: t重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。

2 A' }. m3 A0 j: ]; r" O归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
% I, k6 o% z" \; Y3 G2 a: `, D
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
  h8 u' A  j2 ?; l# G
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
( ?3 t0 C" e9 |4 l5 g. s% ~7 j
" U' n! M6 I2 b1 H% _4 l1 p对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
( n4 M7 ^' p6 }& q% `
$ c6 R; [7 n+ l/ B6 f3 F  }+ p. M接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

' H7 H8 d1 D$ }& s' L将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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 m9 ?' D6 }1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

) z% N2 A6 Z5 ?1 i4 B这个复杂度可以通过分治的思想来解释。
4 g2 j- Q0 X4 s1 S: N6 M. b; M8 J$ ^
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

& |8 W2 S. D/ p- P归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
! B) p, `: h2 n0 j+ {2 w, b
7 u9 ]$ M2 _# G* Y4 y# |5 s& ~1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

2 I+ r3 n+ j2 t0 _" {3 g对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
' O; s2 E6 T$ c( K  W; ~$ N8 |
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
- k8 @+ h7 Z. z/ {5 o& m: Z5 h+ t1 S
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
  b+ g- X& Y  b* K! p
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
9 G5 ?& ^" O/ B9 i
# C" ?! K, R2 M6 k二、代码实现
& {' u* U* u6 S; c9 [2 E& j: k2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):$ @: B5 g) x' `\" @* }/ H
   
2.     if len(arr) <= 1:/ ~; A7 m4 L. E! f: C\" [& V
   
3.         return arr
   - b, B/ X! h& [& n9 k5 I  J
4. . i3 Q& Y8 U5 H
   
5.     # 将数组分成两个部分
   - k$ y8 N\" c7 Q, J0 X, V
6.     mid = len(arr) // 2% V* L# ]! G7 F
   
7.     left_half = arr[:mid]
   8 G8 f. S3 d8 w, W7 L
8.     right_half = arr[mid:]- A( T0 S& w7 _! j7 g9 w
   
9. 
   6 h4 C* W1 I& n- K
10.     # 对左右两部分分别递归调用归并排序
    # |. L& d7 K- x7 Q
11.     left_half = merge_sort(left_half), u; y' p2 _) c2 s  F9 |' y
    
12.     right_half = merge_sort(right_half)/ x: a: P& ]\" h! E- |1 f
    
13. ! c- B/ |) t: t( F0 |
    
14.     # 合并左右两部分
    8 j2 H  u. T2 M& b) }9 z
15.     return merge(left_half, right_half)
    8 x, O. u1 ^9 n  Q  G6 ~4 b/ L
16. 
    2 i: S! B) r( t0 V3 Q
17. def merge(left_half, right_half):
    - F' L3 o: n* ^
18.     i = j = 05 d' Q8 f3 X+ V) k
    
19.     merged = []$ z' `' q# F* A* L* e4 I\" A
    
20. $ z- R8 x4 g9 U/ ?5 b' u& I, k
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中2 l, H6 _\" _: P1 [
    
22.     while i < len(left_half) and j < len(right_half):
    0 J  {- F! B6 ^. V% H: A, k7 @5 {* b
23.         if left_half[i] < right_half[j]:
    ! f$ {9 |3 z8 t# c
24.             merged.append(left_half[i])6 E' y; o/ G. S* w& @\" K
    
25.             i += 1
    , G- \: I. @0 V
26.         else:
      Q% l& i7 h4 y; q* N! z
27.             merged.append(right_half[j])# r; L5 M* W) C7 ^2 c0 d) }
    
28.             j += 1
    3 w% x7 P* n2 W/ G3 l
29. 
    0 m0 O/ o2 I- K' y; p
30.     # 将左右两部分中剩余的元素添加到 merged 中
    - @: j. S+ @: b& u
31.     merged += left_half[i:]8 G, a8 L4 w: y( C  R. l
    
32.     merged += right_half[j:]- ^) E: \/ O- D1 ]  m* M& p
    
33. 
    6 S# f0 D6 }5 Z3 r+ ]- p
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   & O1 `( y4 g9 _2 S/ r9 K3 Y
2.     if len(arr) <= 1:
   8 E$ A1 U9 y5 W- [2 N
3.         return arr5 d) L7 Z/ |6 m! |
   
4. ( G+ ]$ I% R$ u0 @
   
5.     # 将数组分成两个部分* {5 M! D% L- b
   
6.     mid = len(arr) // 2
   & y0 d+ |. K4 r; `1 U
7.     left_half = arr[:mid]
   . [, \1 [) G& i7 e4 x6 W
8.     right_half = arr[mid:]& ~4 t% t7 y6 i; D9 p
   
9. 
   ; y9 u8 i- U- u1 G
10.     # 对左右两部分分别递归调用归并排序3 K) ^& I5 W9 O9 z% t! A
    
11.     left_half = merge_sort(left_half)1 Z) `4 m) I2 g! C8 F8 a/ U
    
12.     right_half = merge_sort(right_half), A/ e8 ?* D9 X  P1 v, S+ Y5 p& B
    
13. 6 W! Q\" f  V7 L, B6 |. j* ]
    
14.     # 合并左右两部分
    1 s3 ^/ f, X% H1 S6 r
15.     return merge(left_half, right_half)
    5 g3 r$ {4 C3 K' }4 c4 W
16. ```
    % }\" i$ l9 V7 a0 f- X1 ?3 \
17. 
    $ l. s$ U7 Z  ]2 Z( U
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    + F$ u% W, ^4 X* y, V

复制代码

merge() 函数

1. def merge(left_half, right_half):( B) o; ^$ Y( ]8 z% F7 V$ i; L
   
2.     i = j = 0
   2 ]7 ~: J6 n7 Y, G5 {! L! n. L
3.     merged = []
   $ o\" _' `1 K8 S, {) ^. ~
4. 
   3 Y/ |/ D2 a$ n' j. F
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中( h8 Q. n  v4 y5 H
   
6.     while i < len(left_half) and j < len(right_half):
   . o: h$ y, T0 Q) \+ P+ A& G
7.         if left_half[i] < right_half[j]:# ?3 G! |$ A+ N
   
8.             merged.append(left_half[i])
   + E* S; Z2 \3 Q. X\" l9 _) D
9.             i += 1; K. O6 m. J4 v$ e& ?' k
   
10.         else:
    / ]# W0 U. ?8 _5 x# @6 H& Q7 u, ^
11.             merged.append(right_half[j])
    $ Q* Z0 B$ v  `+ t\" m3 V
12.             j += 1
    % F# W6 e0 C7 N9 s' q8 h  n
13. $ ]; H9 ~( F3 o+ w  o' W; s
    
14.     # 将左右两部分中剩余的元素添加到 merged 中$ F\" m7 I  R0 D/ r- P9 \0 @0 ~
    
15.     merged += left_half[i:]
    / }1 g& z- `7 B4 }5 ]
16.     merged += right_half[j:]  h$ l* _& b' `# h0 I8 N; v
    
17.   q& d3 A3 e; x3 c1 \$ ^. Y
    
18.     return merged5 W  l- t9 S2 p+ l; K1 r& R. N
    
19. ```' g* V. r. w! P6 X- e1 b' P, q' K
    
20. 4 y4 P; u3 p: P' F- Y
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
/ w0 B+ n, I" c& }( @6 f0 }( Y2 I
6 W& a( v* Y/ ]# }判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
" u- a/ v$ T8 z" o( W7 U7 J
' D( E2 m# {  W8 w3 i6 G) O; M对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

% j9 _* U: y# F* F- n0 ?合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
- D+ s8 [; a) D: i/ K
  Y! m' T- h) Q测试
5 G0 X5 [. C9 J在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   7 l& R# F' @7 n, m
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
# r: a$ a) J" T& e0 J1 d" z( T
! R  K7 f7 O0 S' k总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {
   $ r( s) I0 Q6 `: q* }# F, p% R
2.     public static void main(String[] args) {
   $ x2 `3 u$ |7 D$ |' ]9 ^- c9 L+ i# V
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   / L; E$ o4 h9 g4 F' {! }0 D2 o6 V
4.         mergeSort(arr, 0, arr.length - 1);\" ?; g* R. A4 G9 `: f8 E' }\" P
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   2 L\" {  `8 M3 N8 m+ [. ^
6.     }
   \" P; N+ `6 s4 H\" @) `% h
7. 
   $ F: f+ \9 B9 z3 u% l6 a9 [
8.     public static void mergeSort(int[] arr, int left, int right) {6 F5 f: ~3 y0 `% _& b# o( r3 T$ M- _
   
9.         if (left >= right) {
   8 k' e$ A1 H# T2 U, z' a/ ~
10.             return;
    , {2 _$ J/ K  c8 X) F. K( k
11.         }, ~0 J* }5 m. W; h8 D: {; i7 k
    
12. - P9 B# ^' K  X
    
13.         int mid = (left + right) / 2;6 Q$ Z! z% M+ Z8 Y
    
14.         mergeSort(arr, left, mid);
    9 w, w! \* x! E\" r# j% t1 G/ x
15.         mergeSort(arr, mid + 1, right);; s% D\" o0 c( W' E
    
16.         merge(arr, left, mid, right);
    8 s' G( Z4 E' y8 l/ `* {& l2 g  j1 K/ _
17.     }2 o' q) p* g) @; u- a/ r
    
18. 
    * t+ K  y- N6 t6 k: x
19.     public static void merge(int[] arr, int left, int mid, int right) {
    * y4 S2 Y* N. A. Q. g
20.         int[] temp = new int[right - left + 1];
    0 s! d* y# o( B
21.         int i = left, j = mid + 1, k = 0;6 I( t# s3 ]9 W$ T
    
22. ( U( \  v1 H7 u0 B- u\" J/ j+ i
    
23.         while (i <= mid && j <= right) {
    ' f# W9 F3 m, [* ^\" d/ ]
24.             if (arr[i] < arr[j]) {$ i: ^4 O7 w% d5 R: }
    
25.                 temp[k++] = arr[i++];
    4 `9 V' a! H3 W# Y
26.             } else {
    0 I) g' n4 b6 `) e$ Y\" O3 M
27.                 temp[k++] = arr[j++];
    ! c! ]; I& ?1 Q/ F' e
28.             }, w! z% {0 p- K5 d- a
    
29.         }1 {, @% E* D8 v' f' J
    
30. 
    ; C  ?, e1 b4 q3 v& \$ t
31.         while (i <= mid) {
    4 \& u5 g; b\" w' S\" c
32.             temp[k++] = arr[i++];
    ! y% c! s: U* t, F
33.         }7 j$ r- a$ k\" F4 O, x3 y
    
34. / v5 P2 Q- t3 Y5 Y# K3 _
    
35.         while (j <= right) {8 z3 B. t' {\" a# a9 f; Y8 y
    
36.             temp[k++] = arr[j++];
    / z8 z4 d; s4 b$ s
37.         }5 U3 {: H& b( r/ {+ u
    
38. 
    ) r: o( H4 ~$ D
39.         for (int m = 0; m < temp.length; m++) {
    # a9 A4 q4 S  u% k5 |; q
40.             arr[left + m] = temp[m];/ ]8 K6 H0 z6 ^8 i) c/ t8 w
    
41.         }
    5 D' A7 D$ {: n* B) O! {
42.     }: |- ?! I4 o2 o5 r# i& j
    
43. }

复制代码

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

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

& A; }( J0 L  g# P. W' _4 y* U/ {0 ymergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {. q- F6 p\" m+ a/ L/ y2 K1 Q
   
2.     if (left >= right) {5 }) ]8 {, p+ h; Z
   
3.         return;1 [; h0 j& P- S5 G) ~- d+ @
   
4.     }
   9 p- G. b3 @\" N* W
5. 
   + n; n% }  R$ f4 A  t9 c, d, {
6.     int mid = (left + right) / 2;3 @+ O# K/ a  B\" n
   
7.     mergeSort(arr, left, mid);
   0 _  X# J. l( k& `
8.     mergeSort(arr, mid + 1, right);
   * R5 m& G* s: y: D& ]( u9 ?9 F5 s( V
9.     merge(arr, left, mid, right);
   $ \3 V4 i7 e2 P2 ?- v7 \/ m9 h. B
10. }
    \" b( L. N/ f2 P: N' \. N( }2 z4 N
11.   ~; t# [% S* [$ S
    

复制代码

这个函数使用递归的方式对数组进行排序。

& s% g5 a) Z; V: E. s+ E对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   ! P5 ~/ J- F7 x8 r7 x
2.     int[] temp = new int[right - left + 1];
   3 i; p$ [\" u! [/ F- a2 u
3.     int i = left, j = mid + 1, k = 0;
   8 H8 s' M) A7 E' }7 B6 F  m
4. 
   7 W8 P0 {* r3 I/ A% a4 j7 _- k
5.     while (i <= mid && j <= right) {
   # J* W% g  Z* U- v( Q
6.         if (arr[i] < arr[j]) {1 S. t* z5 c7 t# [. D+ M5 L# \
   
7.             temp[k++] = arr[i++];
   $ R! Z7 j6 r6 V/ j
8.         } else {5 l; j. X8 x\" X5 l1 T
   
9.             temp[k++] = arr[j++];) ^5 v( u. Q: m; {* e0 `; F
   
10.         }
    ) l9 c8 z, @' f. L
11.     }
    $ {  k. X, z\" o, |- j5 z  D
12. 
    , F7 K2 Y5 u5 d
13.     while (i <= mid) {8 [' B3 q( N( {2 m* Z+ z0 l
    
14.         temp[k++] = arr[i++];
    % @( [4 r0 J8 p) Y. h8 \* f
15.     }/ l1 z) v3 d, ]( W7 D\" P* _2 t+ U% i
    
16. 
    : F4 {: F$ j/ P8 x
17.     while (j <= right) {
    ! i# f# S. C# D$ c! j8 ~
18.         temp[k++] = arr[j++];
    8 n& m5 {; N/ n+ G; y
19.     }
    ( r8 \2 u9 ?+ E* r% y. L
20. 
    8 }6 O7 k) d: H; w6 Z
21.     for (int m = 0; m < temp.length; m++) {
    0 C7 h' Y# S' X
22.         arr[left + m] = temp[m];
    0 P0 e2 R- L! H  f' n4 g
23.     }
    ! c# B8 [2 }5 Z! s$ s7 e' K
24. }' j# W& V' [) x. X' v, ]- a0 _
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
9 k' M9 \% f8 X# `
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
" @/ {% T/ P8 N; S( x% s; k
9 j( |* K- x5 c& ]最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
. q; L- K; s) g
% L2 [2 B" w6 T1 }( k需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。


. Z# q/ a! D3 p- L

- ?. a. l  L9 Q3 k1 G
! [- s3 X5 ?8 a$ Y0 q9 \* y
( x% p' O2 D% q
; i1 v/ N- N0 N