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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
( d1 p4 R6 w; V1 b* D+ ?0 O
以下是一些常见的排序算法：

冒泡排序（Bubble Sort）
+ `  \" ]. X  v7 D  ?& P
插入排序（Insertion Sort）
& Z* z8 C# A0 u% |  X* {+ ?+ z9 M
选择排序（Selection Sort）

, a# h. b4 o+ ~( L) ^' e$ O归并排序（Merge Sort）
  ]4 ?6 k' B: ^! B( l
1 f% U0 O" U" |5 o& h) S* a& v# e# [快速排序（Quick Sort）
2 i- y3 O) X% \
. F! N0 C! _0 C8 O; P7 I' Q# _堆排序（Heap Sort）

一、基本介绍介绍
1.1 原理介绍
7 x) M  Q3 s" `归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
; U" W: l& ?6 l9 x* v$ v. G/ ]
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
. A6 z) p: i( T! r$ E; d3 m: z7 Z+ {- B
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

4 r7 Z) k1 y( A# C7 p定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
" f; ^4 G6 \) i& f
" F+ L' k3 c0 g比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
- w  Z3 L5 O0 \. h$ j
将另一个数组中剩余的元素放入 C 中。

# Q. Q9 s3 k: }7 n( r6 w  S归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
' c8 Y9 B( q% j; f3 w
8 U& V9 s8 r- A* @假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
1 @2 C" ]1 R9 L1 h  h$ S  j7 E: `
! }1 M& }+ j& V首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

+ x( Z# T  F& Y% O$ O  A对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
+ |! R0 M6 j% g/ ^( G6 D
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。
* J0 `7 u) h  S0 l' e3 g
1.2 复杂度
+ {/ ^8 n: s5 K2 e* e6 X8 f; b5 I归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
& |+ R1 V0 X+ n+ y% f+ e
这个复杂度可以通过分治的思想来解释。
1 h: h( [6 q. ?* D0 Z
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

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

* p9 W$ ~" N( U) s. y& \归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

9 U, a$ _0 ]! `/ f7 K' q$ {这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
* V+ S& f- Z& j( a3 o# y( ?/ g
1.3使用场景
0 p( X! p# Z; p1 W5 G# k归并排序的应用场景比较广泛，主要适用于以下几种情况：

0 R1 Z( p5 ]* c( Q6 r% i8 Y" I8 J; E+ f对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
- B7 P$ {' N4 u5 g6 k, F- u
8 `: C& z/ t2 A. W( G/ K对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

. _# D) g& U; u  {! o" V' X对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
! ~4 k3 `# A" T0 B4 g+ p0 o" B
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
) L" M% b/ @0 L' n+ e6 m, s
( W! |1 s5 P; }2 R3 @对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
3 v. }4 G7 h' _# ~: t1 l) Z
7 q9 D3 g8 k- P总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
4 X6 y# v7 ]5 G) H2 n
二、代码实现
( X$ m1 B% I; ]3 ?. |. X2.1 Python 实现
8 F3 R5 n3 o! c# v) h: j以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   4 M# L' H  L% @8 ^
2.     if len(arr) <= 1:\" H# M% I. Z. l! i+ }0 R
   
3.         return arr
   5 \6 y0 X$ g2 p% c. |5 @
4. $ V. I- v- U# M. T- {
   
5.     # 将数组分成两个部分
   - o  ?& i* E, Q1 z7 O* Q! T
6.     mid = len(arr) // 2
   ( {# R7 l8 i3 {  ^
7.     left_half = arr[:mid]
   \" n& Y$ r9 A7 ]# j0 ^\" y4 w1 R
8.     right_half = arr[mid:]$ {2 _0 J% u9 r3 v
   
9. + z7 ~5 w9 ^' M\" [% d& Q7 ~: @' C
   
10.     # 对左右两部分分别递归调用归并排序
    6 n: v% H# n) t; D+ c
11.     left_half = merge_sort(left_half)( a* V\" U  |8 @; u
    
12.     right_half = merge_sort(right_half)- X) K* T5 v! g. V0 ?
    
13. 
    3 l, ^% W\" J' o
14.     # 合并左右两部分* z4 R$ z7 I$ |
    
15.     return merge(left_half, right_half)9 E' U9 N7 F, e  ^' h( L
    
16. / r+ v/ u- r/ ^! K; s* K8 U) x
    
17. def merge(left_half, right_half):
    ! ~. D: E9 U8 H, W
18.     i = j = 0
    3 J\" `' _. f4 q- a# i5 \2 }
19.     merged = []) h: @2 K( j\" v$ ^. }8 n) n! s, R; E
    
20. 0 p) y$ @5 P# E+ u% b0 e3 c
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中( l9 C# j' X) w
    
22.     while i < len(left_half) and j < len(right_half):5 Z/ {; l7 _. z) q/ t8 B
    
23.         if left_half[i] < right_half[j]:6 K+ h' Y2 }; K- n. ?5 G5 A
    
24.             merged.append(left_half[i]), F\" j/ C7 E8 F/ d
    
25.             i += 14 D* |( x$ e7 O
    
26.         else:
    ; O* L( |8 X6 R5 Q
27.             merged.append(right_half[j])! w0 F3 @; @! t# Y/ Y/ c
    
28.             j += 17 r% Y4 R8 _7 y% e
    
29. 3 R; w, F; t. z( U
    
30.     # 将左右两部分中剩余的元素添加到 merged 中\" C( V5 S, j& e- a1 \3 l( J; o
    
31.     merged += left_half[i:]
    8 i/ H2 o3 e& u( E+ m/ X% o1 ^
32.     merged += right_half[j:]\" m+ n9 A; a: G\" f- w) L) _
    
33. 
    + D' a. z- u- `$ h5 @% l3 Y& A: ?
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):7 Q4 j7 B3 i8 n8 {
   
2.     if len(arr) <= 1:
   7 ?& ~) y% E\" r9 O4 w
3.         return arr& s\" X2 l) c, ~; |! t- L# E, ]5 [% R
   
4. 
   \" A3 S& s' O, ?
5.     # 将数组分成两个部分
   \" S6 s, z2 P  v. B; s/ [
6.     mid = len(arr) // 2
   - n( H9 T6 K, O6 ?
7.     left_half = arr[:mid]+ ?$ Q1 Y! d' N+ O/ G- K( z
   
8.     right_half = arr[mid:]5 q  A& o+ V; q1 \  ]) P
   
9. 
   4 j9 O9 g! B, G  F
10.     # 对左右两部分分别递归调用归并排序
    $ s# y  E# K8 i& i
11.     left_half = merge_sort(left_half)
    * N3 J5 F6 o0 w- h
12.     right_half = merge_sort(right_half)9 U( m% V3 e6 `4 H$ ~0 \3 k& `
    
13. 
    6 O$ N# ^1 S( w+ t5 }  \7 Y
14.     # 合并左右两部分! l1 S  @$ R) s, H
    
15.     return merge(left_half, right_half)
    9 m. h- |: m+ u: i: r% [
16. ```/ m) P) ^  F0 z. X) Y# q
    
17. 
    & |1 K# ?, i- N  }\" C. L
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。6 [  z* R! g# U5 E
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   1 P\" d% {* H& d* R2 A0 j/ Q! F
2.     i = j = 0$ q. {\" t; s8 X) \
   
3.     merged = []
   % B6 C) R; T' [$ q# G) e
4. 1 G) H2 y4 x! e1 l% w; O
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   5 h* x1 z1 T# y7 E  P' o
6.     while i < len(left_half) and j < len(right_half):
   , {6 I1 [& x; K, M  X, t
7.         if left_half[i] < right_half[j]:3 O5 V4 K' B2 D4 q3 G8 H
   
8.             merged.append(left_half[i])
   8 A1 w: d) f! _* h
9.             i += 1
   9 M1 a. Z( X. D+ y, n$ k% P
10.         else:
    ' m3 n2 c, J) o) C8 ]. Z- s6 y
11.             merged.append(right_half[j])
    : k& D/ J; `) X; |% t  y
12.             j += 1
    & z* a$ r% i& z
13. 
    - H$ a\" P) i7 F1 P
14.     # 将左右两部分中剩余的元素添加到 merged 中\" b' O% T* Y1 W& X
    
15.     merged += left_half[i:]1 b0 }5 h3 O+ V& s
    
16.     merged += right_half[j:]
    , d. V2 s* e2 y8 @5 g
17. 
      \6 X/ x9 g! M, G: S* m
18.     return merged3 R0 y' g$ y$ y% a
    
19. ```* M2 N8 h3 B9 K+ U6 A% m0 A
    
20. 1 e& A/ Y& d+ d. y
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

2 n# G8 c) f2 i( H$ {判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

$ _3 v" s! Z, D  A( p将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
! L4 i0 h; k* M& {! \: j4 R3 u
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
" S: z  n% ^( _  T$ q, x$ r
测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]* @6 L1 G- N4 `+ Z\" K# c) A
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
. Q' \& N3 j  M! ^, m; A
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {
   : V8 R$ @# K9 `, J9 ^1 w
2.     public static void main(String[] args) {
   3 L* l$ @( O( w% W- Q* I) h
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};$ `' J4 z$ y6 f( o8 j( q8 r
   
4.         mergeSort(arr, 0, arr.length - 1);, y; D3 P& e  I3 k
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]. I6 y# Y) I6 t2 B( F, C. d
   
6.     }4 M  \% ^0 s7 T  D. z( G
   
7. 0 I, N4 z' I- i. G% ]+ x$ p
   
8.     public static void mergeSort(int[] arr, int left, int right) {0 \! R  p+ Z. I( ]
   
9.         if (left >= right) {
   $ A# h7 e1 C* Z' |* ?& N0 j
10.             return;
    3 U9 H1 m5 Z9 e+ B\" R+ N
11.         }
    $ R1 O  @3 {! v2 N, v6 m
12. ! b% [  ?\" z! j3 k
    
13.         int mid = (left + right) / 2;7 X2 x; \) e! k3 N0 i% s. I
    
14.         mergeSort(arr, left, mid);
    4 {3 }7 x8 N% i7 Q' L, C. A) B
15.         mergeSort(arr, mid + 1, right);
    1 v' R1 ~3 t* j3 F8 s( R( w7 m% c
16.         merge(arr, left, mid, right);
    9 L, {; G4 p. J# y  L- o
17.     }
    $ L* [) S9 m- h+ p
18. 
    9 e; g, y( a' `/ M
19.     public static void merge(int[] arr, int left, int mid, int right) {3 Z  ^) q0 H. I9 k4 d! q# H
    
20.         int[] temp = new int[right - left + 1];; {: x  n$ l8 G% z
    
21.         int i = left, j = mid + 1, k = 0;) q+ m! q1 D+ }# r; c+ ~
    
22. 
    ( N3 `% b4 y9 J) m% e
23.         while (i <= mid && j <= right) {6 }. p  e4 t4 t! J4 b$ x  S3 k: C
    
24.             if (arr[i] < arr[j]) {8 m8 v1 O2 e6 l/ [
    
25.                 temp[k++] = arr[i++];
    \" i\" n0 S; L: [8 ?
26.             } else {6 {6 F' }9 ]/ G  M) z
    
27.                 temp[k++] = arr[j++];& Q, K2 N6 F4 H% m! q. z
    
28.             }3 T2 R8 V8 J: g) t% g
    
29.         }
    2 v5 i3 A  N: @6 q* j
30. ( x3 L8 B8 V) j. L: `3 M1 }6 F( N$ p
    
31.         while (i <= mid) {7 u) B0 Y# W( _* F4 h! Q
    
32.             temp[k++] = arr[i++];+ D- R/ n& x& K  E; @; B- N
    
33.         }
    & t. [( m3 l4 V7 M6 D1 ]  m
34. ; I6 M' m/ w. E
    
35.         while (j <= right) {9 ~1 Q* A3 v5 T# K2 p; C
    
36.             temp[k++] = arr[j++];6 L5 e1 t6 w8 d4 o; r& `% N
    
37.         }
      X( k\" B) ~4 @; j6 l2 S8 d3 p\" [
38. ; U/ |& p  C. [2 j/ R8 l
    
39.         for (int m = 0; m < temp.length; m++) {  r6 n+ w) Z$ g1 D% u2 _; d
    
40.             arr[left + m] = temp[m];
    2 \0 C8 }1 b. X
41.         }7 X6 y. q! B7 Y
    
42.     }# t6 E  D; j0 @/ F3 C, w
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   $ t7 \7 {\" f1 u+ p
2.     if (left >= right) {# t. V' M/ D) D1 _. o
   
3.         return;4 |) `* B, Y. M, y9 l3 [
   
4.     }
   6 x/ J3 O. r, E  u, Q9 ?
5. 4 T. R- p# l  B% R! Z
   
6.     int mid = (left + right) / 2;
   $ U6 f2 u4 ~5 P6 i
7.     mergeSort(arr, left, mid);! k* t1 Q- E, M+ }  u0 Z( h8 @
   
8.     mergeSort(arr, mid + 1, right);
   ! I( ~5 e  s0 ?% g, y
9.     merge(arr, left, mid, right);* E. w. M# P* T5 Z
   
10. }
    $ o- ~! N  k9 E9 j. d- ~\" z0 |
11. 5 B: a: p  Q1 a5 u3 a- _% K
    

复制代码

这个函数使用递归的方式对数组进行排序。
2 D3 y8 F! b/ u1 n
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {! F- h' D5 Z7 |: j
   
2.     int[] temp = new int[right - left + 1];
   \" {4 L8 ?7 j, ~( `! ~9 D
3.     int i = left, j = mid + 1, k = 0;/ H, x: {6 y5 P7 ^
   
4. 
   , e/ u2 H. D& y2 S  r
5.     while (i <= mid && j <= right) {( M0 Z' _1 ^/ c5 N9 p1 f
   
6.         if (arr[i] < arr[j]) {
   2 o9 Q8 `\" n5 b2 M, m\" e
7.             temp[k++] = arr[i++];4 f! V& q+ U7 v9 l: |8 z
   
8.         } else {5 ]* y, [: E( y5 M) l+ O( |& Y
   
9.             temp[k++] = arr[j++];, i2 b# D. }' W9 P) ]
   
10.         }. J5 b! x% N1 m0 A. a! z
    
11.     }* J; x* Q5 }) I/ R8 i
    
12. 
    - K) v3 l8 V, z# k
13.     while (i <= mid) {
    : x6 w3 ~  O1 A* O% {  F0 r: M( _
14.         temp[k++] = arr[i++];# k! t- U1 a& x. ?6 v
    
15.     }$ S% J# J' R5 Z/ r: ?1 @6 z
    
16. 
    . ~+ R8 N  ^- [. R& i& ^
17.     while (j <= right) {! [% a- s% b) Z5 p* u: s8 V1 k9 X5 _
    
18.         temp[k++] = arr[j++];7 c6 K/ W( [\" O\" \0 m- a
    
19.     }
    # V\" M! ~0 b! U6 Z' K- e
20. 
    7 v; j8 X9 m. e+ S0 R+ k: D, U; h! d7 F
21.     for (int m = 0; m < temp.length; m++) {) a: A0 c& Z8 Z7 ~
    
22.         arr[left + m] = temp[m];/ j' p$ k1 M- j, L/ Z' C* p# Q4 l/ U
    
23.     }
    2 Z2 N( a6 l) q
24. }7 m* u, ?8 P# [& g! p3 ?
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。

合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

- \5 Y; B( p5 p7 I6 `最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
: c& x, E5 R+ k3 U$ {9 z
需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
8 v- `8 R+ z5 o# ^, v9 ]
6 ?' o4 Z- @4 e1 _8 e$ @  x这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
- _, }1 c" q/ r" ^! k) n

( _0 k- T( F  X. d: b
' J; s( X2 L0 O' l, u* a* R- z9 O
+ X' T4 x( i7 M8 M" G


; m6 F# r; b9 D: ~; z0 |8 F: s! `