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

2744557306

1 基础介绍
4 n/ A2 S* ?) B1 i1 Y. {6 i3 r排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

以下是一些常见的排序算法：

$ t  R' [6 \* K8 E/ h3 _0 y! O冒泡排序（Bubble Sort）

0 U" d, X- x! ]0 j/ i插入排序（Insertion Sort）
  Q! L! ]  M/ p+ g- M- b! D/ l
选择排序（Selection Sort）
  O! N& {5 V& v; w& _
归并排序（Merge Sort）
  t* o7 F6 c9 m8 A! f  M
快速排序（Quick Sort）

7 H. j+ _6 V- \# @5 ]堆排序（Heap Sort）

: H6 {+ I& j, r9 K1 P2 Y/ ^一、基本介绍介绍
1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

$ o9 H3 z3 B' H4 A- j# g8 [6 C归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
) o0 I4 o% n  x
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
& z/ t2 m* T9 d6 d& O
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
3 u- S! r: E% _
合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
2 |2 z" {7 ^9 c* W6 K) g
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
0 d% u6 V+ B3 r8 D8 l+ u  Z
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
* n, l. K" j" ~5 O: V0 d
重复步骤 2，直到其中一个数组的元素全部放入 C 中。
4 b9 x" Y$ q1 d2 K* e/ r7 y
将另一个数组中剩余的元素放入 C 中。

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

原理简单示例
  r5 i6 I' \+ K& P0 d( Q以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
7 ]* }6 h6 Z1 @8 Z& W
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

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

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

0 N% H$ u7 q( q! |对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

1 s/ d+ R# r( }/ s2 Q* |7 D将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
" R( `, B% [! c' g* _$ e
, U% Z8 z' t+ \8 X3 S0 a因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

5 n/ r, [. V4 M1 H; c1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
, `3 T  n7 |' ?( x  u8 D3 B! l  v
这个复杂度可以通过分治的思想来解释。

& K9 d3 S+ S: |* e4 r- V7 l$ s首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
5 p* p& o& N: U3 V
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
- J% [5 C3 y1 n- y
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

  K, c' |) s9 [7 P3 D# G4 p0 t! Q6 c这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
9 b: D- k4 a9 ^
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
8 z( ~! H2 I" o; W# b% O
% O4 [  ^1 J2 ]" d6 q对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
2 C7 i* o- Y" U( N8 ^" [
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

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

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
: u9 g' |# }3 P; z' G' y3 b
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
3 {( I, V& f0 p% u
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
1 ^' V( x- ~6 k% n
二、代码实现
+ P4 Y" b; v! [2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   * [/ p4 q# O1 U; f) }
2.     if len(arr) <= 1:, }\" g/ D+ H  s% N4 h( ~
   
3.         return arr
   ! N+ {) y+ V& v5 z# o' L3 ~. {
4. ! o# U: g# b' p% i/ N3 N+ a
   
5.     # 将数组分成两个部分
   / c! ~1 Y( O7 Y! S# ~' r& g
6.     mid = len(arr) // 2
   ) x  j+ d5 P$ ~: U( A
7.     left_half = arr[:mid]
   : }: \/ J) t, a2 q7 b5 \
8.     right_half = arr[mid:]
   : g5 P  R9 A1 s0 g. F
9. 
   0 h( K5 ~6 y3 U/ z6 P& f
10.     # 对左右两部分分别递归调用归并排序\" a( G3 o1 u: h) C; q# L7 ?
    
11.     left_half = merge_sort(left_half)6 i! P  C+ Q8 S+ m2 }( V3 u
    
12.     right_half = merge_sort(right_half)  t( F4 b/ h8 l( ]* B1 G
    
13. 4 J6 Z* Q9 I8 V3 H1 ^
    
14.     # 合并左右两部分
    . C! g) N# ]! K* c1 b6 w9 j& O, [* g
15.     return merge(left_half, right_half)
    ! L( j; b+ U3 ]9 ^; i' |
16. 8 f0 M& i, \8 K! F/ a  L' _
    
17. def merge(left_half, right_half):
    & k0 u7 S* z! C% `
18.     i = j = 0: p2 }9 O& c' F\" ]
    
19.     merged = []
    / ]8 s7 q! s# e+ o+ F9 e# w: m8 c
20. 
    * `# c* _: Z. [$ c: A9 Q
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中/ J0 J, r' r, ?
    
22.     while i < len(left_half) and j < len(right_half):, U( d4 D' U  U% Y( k
    
23.         if left_half[i] < right_half[j]:2 ?2 I; c3 W! P, m' X
    
24.             merged.append(left_half[i])
    ( ~& ]' b9 J) W1 C' P
25.             i += 1( K. B& N* A1 N. D. J6 m$ o6 q  \
    
26.         else:4 t4 M8 Q( J* v& D1 a& h
    
27.             merged.append(right_half[j])
    % m' \7 C: p0 h3 A! f/ F
28.             j += 1\" k) s/ s# J' h! V4 e& t+ c
    
29. 
    $ |5 s# j1 ~: u# ^9 k\" H
30.     # 将左右两部分中剩余的元素添加到 merged 中5 ?* ~, V* a! k\" `, c( F% v
    
31.     merged += left_half[i:]
    * C& y% R/ q# I
32.     merged += right_half[j:]
    ) l% Q0 t1 X8 b3 X3 U4 u& l$ M6 b
33. 
    ( X  Y7 m1 B6 j  h
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   7 ^, k$ h% M; U\" X, t, `
2.     if len(arr) <= 1:
   & q* `, P/ N4 X
3.         return arr+ \* Q( M7 s: S7 t
   
4. 
   3 k8 V, R' H3 ^; N( a+ V% f
5.     # 将数组分成两个部分: Y2 d4 @9 f1 y\" N8 O5 k4 S  P0 j
   
6.     mid = len(arr) // 28 U8 Q7 F: E& e) p% G+ A
   
7.     left_half = arr[:mid]0 V, w! D; U* j# X6 i/ y
   
8.     right_half = arr[mid:]' q7 B7 @! u, k; p$ ]
   
9. 
   # p. a- V8 F2 C! G7 r5 F
10.     # 对左右两部分分别递归调用归并排序
    $ [' c  w+ d5 G
11.     left_half = merge_sort(left_half)% R' e& B3 q0 \! o5 N# @
    
12.     right_half = merge_sort(right_half)
    6 A) e, r\" A/ j( u
13. 
    7 s. e# `0 ?: J; `2 a5 O. f2 C4 C9 s
14.     # 合并左右两部分6 c\" ^: a8 h1 g& q) ^# F
    
15.     return merge(left_half, right_half)
    % z, e: e+ I! G1 ^, f3 ^! m
16. ```5 U6 T8 c\" Y8 I\" p- k* A
    
17. ( k- K0 c% ?$ L8 M* q7 a3 {
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    + u5 T- X' |% H- o7 t

复制代码

merge() 函数

1. def merge(left_half, right_half):
   % h; D' D( V; P3 {/ m$ L: E/ o
2.     i = j = 0) V  |, r, u% w8 |1 t\" f& e# N
   
3.     merged = []- @- _- e; z& f\" U
   
4. 
   , n' D2 W& s4 S- Q8 C. d. b
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中3 d7 a) N9 v3 T* T6 F& i
   
6.     while i < len(left_half) and j < len(right_half):
   ' V3 F+ b, i* K2 n! o. b( |4 {
7.         if left_half[i] < right_half[j]:
   ) W1 m7 }. z$ H* p: b9 M; N
8.             merged.append(left_half[i])
   \" v  o. @- F# t! ^1 _/ @  {
9.             i += 16 ^/ T+ E$ t# b8 d& m$ \: _
   
10.         else:
    ) n  {\" f+ @, N4 F! m
11.             merged.append(right_half[j])
    - X# a4 j( C  J; _
12.             j += 13 @9 t1 R5 ^) G\" ^+ Z- k% g
    
13. 
    / @. _. h0 u- k9 B) O6 R
14.     # 将左右两部分中剩余的元素添加到 merged 中8 ~& [/ d+ ^2 r! j
    
15.     merged += left_half[i:]1 n) L: \3 c0 Q: o/ `7 b! f\" B\" I
    
16.     merged += right_half[j:]
    , B/ V1 {; ?/ P! G
17. 
    9 A8 }' r; P; J0 t
18.     return merged\" ?& |5 p* t+ o( p* s- C8 l
    
19. ```) o% O3 p/ ~. l& @1 h. ?, x. r
    
20. 
    1 I8 m- A: l5 l8 P
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
0 b1 O( k. j, m0 [, V  {; I6 Y
  g2 G6 ^3 @8 v) C判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
; t+ S( X% |# B
将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

, j- {2 \: E1 I: G- C+ `, O对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

- i; k! R8 C! s- v. e$ q  N; S合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
; {% e: P6 E) {6 ^
测试
: B2 A' y. R& T6 H1 T6 G9 O在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   / ]) Q: o) h4 T' g9 Z
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
3 d2 b7 j; o; v. [1 J' r
7 C- j1 b. A  x" Z  [' o9 c4 R总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
! F9 M/ R; F% D8 D; C2.2Java实现

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

1. public class MergeSort {
   2 |! t; k; u9 K  w7 @\" `
2.     public static void main(String[] args) {8 t, P, k* N+ i\" |
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};& r5 H: @1 x( p2 B  Y/ R\" ~
   
4.         mergeSort(arr, 0, arr.length - 1);
   ( U6 b  M; w, F! `( P
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]; k7 T9 J9 r4 a. g7 e1 d
   
6.     }* i: B$ y3 |1 i- K' {2 S6 y0 [
   
7. 3 B3 ?7 N& H4 Q2 w
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   5 X5 z& ?  o) R\" p8 H
9.         if (left >= right) {
   5 H8 K) V: [9 T: @; A
10.             return;
    & M0 s+ u6 h- o# O9 k4 _
11.         }
    ' l. @+ r5 Z, S/ l3 R  e
12. 2 i( D# |7 H3 \. `
    
13.         int mid = (left + right) / 2;$ [  ~# _\" U\" n8 v
    
14.         mergeSort(arr, left, mid);
    - L- t# z# N+ n9 n) i( ]- u
15.         mergeSort(arr, mid + 1, right);6 e8 P, ?4 I8 s$ S\" I
    
16.         merge(arr, left, mid, right);
    0 ~; p6 y5 ]! h/ Q/ W! A* U
17.     }
    1 |# d2 F/ k\" v: G
18. * b8 Y: Y; S1 ^) D2 n
    
19.     public static void merge(int[] arr, int left, int mid, int right) {8 g# M; i& }+ R8 C$ R! A
    
20.         int[] temp = new int[right - left + 1];
    * w* D/ G( _! J  x: `- X
21.         int i = left, j = mid + 1, k = 0;& @  |5 W  O5 b# i' }
    
22. 2 n$ V, E% N6 Z
    
23.         while (i <= mid && j <= right) {
    \" N8 d. j) l* O; `6 G7 t+ k
24.             if (arr[i] < arr[j]) {0 i5 Y4 v' A. ?, B- p+ C& F7 _
    
25.                 temp[k++] = arr[i++];1 z+ V1 y; W( _* {4 v
    
26.             } else {
    $ K: C/ A% H# Y9 y
27.                 temp[k++] = arr[j++];. z1 }# T/ b4 [0 N\" b9 i; N0 L
    
28.             }
    ) e7 `4 t+ _( B. ]0 y
29.         }\" c+ k  \- m( U8 g) O
    
30. 
    8 i! H3 K* h) y% U2 f8 \0 H# l
31.         while (i <= mid) {
    # I) i9 }0 w! u
32.             temp[k++] = arr[i++];3 s( V. R$ b\" D  U: v
    
33.         }
    ; n\" W4 P- ?: S1 o5 Q/ @! [
34. 
    , T+ T: |\" i2 X2 d2 w3 n& j
35.         while (j <= right) {/ T, j, e) _/ c# p& @& ?
    
36.             temp[k++] = arr[j++];: n7 B: o2 G5 M# y
    
37.         }% z' y. U3 q- j6 G8 j# [: S7 ^% \
    
38. 7 j( }+ j% ]8 \2 L, D( `
    
39.         for (int m = 0; m < temp.length; m++) {
    & W+ t& R% J& Z& L3 X' P: ]
40.             arr[left + m] = temp[m];
    $ J& |  v2 A6 ]( C8 M% T! Q4 V
41.         }
    5 A6 A$ v\" _# m9 j- c
42.     }& n\" g3 b1 v\" I4 w: u
    
43. }

复制代码

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

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

0 `5 R  C2 r9 N- ^6 V: ]: e* pmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   3 a9 z4 V1 b7 v* l' r
2.     if (left >= right) {
   + L9 N. r  X# s/ D3 O
3.         return;: E3 L% C, ?8 V$ _3 u
   
4.     }/ R$ N- C: F. |+ F0 i\" R
   
5. 
   8 h2 K+ c6 Q* [8 v3 A
6.     int mid = (left + right) / 2;. F3 \6 L$ x\" [1 d6 L+ N
   
7.     mergeSort(arr, left, mid);% P- {% s& ?& n) f3 T
   
8.     mergeSort(arr, mid + 1, right);
   8 x) K, v/ C2 O5 N2 R$ C
9.     merge(arr, left, mid, right);
   ( i% E$ _* }7 H6 V3 J9 n
10. }
    8 S  b2 R0 q# z4 R; M
11. - i6 Y\" {6 _+ L* s: \4 m
    

复制代码

这个函数使用递归的方式对数组进行排序。
, }1 N( a4 ^  v& P. j
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {+ O7 I  m* `( H
   
2.     int[] temp = new int[right - left + 1];1 R+ ~0 g: X8 X
   
3.     int i = left, j = mid + 1, k = 0;
   # S7 n+ q6 U# I, A
4. 5 B1 t: A; S. c9 U5 D1 n0 m
   
5.     while (i <= mid && j <= right) {9 S& q% z3 E  a& o0 u8 d) o) F0 i6 n
   
6.         if (arr[i] < arr[j]) {. E' k: |% ?5 l1 ?* z7 O
   
7.             temp[k++] = arr[i++];9 H0 s2 {; N  d\" x\" o% c
   
8.         } else {
   # n3 {0 O/ e4 h
9.             temp[k++] = arr[j++];/ m( F' B: E3 w
   
10.         }- h6 l9 W% C8 U4 ^
    
11.     }! `; r' [: q( r3 F1 [2 [
    
12. 
    9 a9 l\" O/ T) ^\" V; Z
13.     while (i <= mid) {0 ]  L* J7 I1 V- u4 \9 d6 ?' g( ^
    
14.         temp[k++] = arr[i++];
    + v2 e5 Y2 P, O$ h
15.     }\" y6 f9 v& T: `0 r' k) }; Q
    
16. 
    : [# Z3 ^2 z8 Q# z& D# A
17.     while (j <= right) {! \- K; U+ f+ n9 p- D6 q
    
18.         temp[k++] = arr[j++];# ~' z& C2 B\" K0 I: g; H9 Q. o1 l
    
19.     }
    * h\" J, P- q; z7 n
20. 
    % R$ i3 C- d$ g: ?9 _/ y
21.     for (int m = 0; m < temp.length; m++) {
    & q% z1 n$ E. [& r, A( g
22.         arr[left + m] = temp[m];) U/ P& E7 y3 Z$ F
    
23.     }
    + u. D$ U! H) e7 |3 K7 z5 m
24. }
    # |4 O  Z8 r9 [2 _/ g

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
  T2 L9 V8 g3 n. d  v
$ v7 k+ _; \6 A: w6 q5 |) E- c5 Y合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
$ N7 r! I+ d7 W3 y7 R4 g, C
& q6 L) |5 {: w$ u4 g- Y需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
2 h7 p& j& o  Z1 `1 k" Q$ T' G
/ Z' ~9 p9 ~% R! N3 t+ k这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
/ k: {- \' k9 `& l6 P' W: E


0 H* N9 O+ v, y1 x, ?4 U
5 w* D8 E  `' F6 v' Q4 _0 S7 ^4 ~7 f

. A' t9 i4 P4 z2 l2 `
( u. b+ q0 m0 V! ]