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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
6 \! M; F% P, U7 [, j* O! `
以下是一些常见的排序算法：

3 o6 U% E; ^; t+ w冒泡排序（Bubble Sort）

插入排序（Insertion Sort）
9 n3 Y, F* f+ E* n
, N* y" w6 P1 B+ ~+ a选择排序（Selection Sort）
, h7 l5 w+ K& r9 o  e0 V0 a
: U# C/ d" _+ w' E归并排序（Merge Sort）

8 v% q- e( \4 ?快速排序（Quick Sort）
- b- W( G( z4 _) r( T- N6 q
/ ], D; ]3 ?( c) y- K# b% K: G/ [堆排序（Heap Sort）
. u& t9 K6 Z& U! Q% m- U1 G$ ]
一、基本介绍介绍
1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
1 R1 w9 a# k9 O0 \$ X: ^+ n$ u
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
6 B  B) ~$ E* z
- J" v7 N4 L9 K分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
( r) p& K! ~4 d: }3 K
合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
$ z* T) |7 @; n- `& E6 B
4 U$ I8 b4 }  f# E" [; d定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

/ U7 \+ e" b+ U比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
0 s, S5 H  |2 i- `, W5 E9 F3 B
将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
5 D. n, O5 ~' H! o+ V; C
原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
0 W  @) W& l: P" A3 X' h! u
  d0 ]( i+ ?. {- W# f/ V5 E对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

# w# U  H) b% I7 E& ]接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。
/ V3 |) i% o; g
) ?& K8 Q) ]# `9 M4 U因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
" [" p9 P% t$ z$ F1 `
1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

这个复杂度可以通过分治的思想来解释。
" i) U, f5 a& C9 x5 b
9 ?* a  z+ V0 M, |! o8 S首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
- \- Z/ Z1 K+ p) i+ d* I- \
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

7 U4 h9 m$ [4 L8 i% Y; y- t( q# Z1.3使用场景
6 A! J: z, ]1 j. j归并排序的应用场景比较广泛，主要适用于以下几种情况：

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

5 C* H3 }) A0 y2 q( @; b$ S对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
( @4 ?7 r6 l6 [2 S) E# n
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

) P+ Q* R6 k1 v对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
1 ]: q, t: c, Q* B) @- `; m; `0 Z
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

, F' B  g- C" ^2 i, W( `. U总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
, B9 [! E5 ?3 }
4 |3 G7 R& _* b; N二、代码实现
2.1 Python 实现
5 [' Z7 ?3 `5 u" T9 L以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):( i( u) X, O6 _) ?/ g! ~0 a
   
2.     if len(arr) <= 1:
   ; c& b# F  H9 k( D8 K
3.         return arr6 L' M\" ^) |3 E0 h  u\" N% v
   
4. 2 k0 g1 j$ y* G% O4 X/ i% [
   
5.     # 将数组分成两个部分
   . n. k5 G/ B) B
6.     mid = len(arr) // 2
   8 V\" S2 w6 V/ M2 Y
7.     left_half = arr[:mid]
   \" F) v' Z9 X. u* _. Q
8.     right_half = arr[mid:]
   6 p- |, z9 e/ i) d
9. 
   4 Z+ o0 C$ p\" {1 O
10.     # 对左右两部分分别递归调用归并排序1 f& {8 o5 ]$ W
    
11.     left_half = merge_sort(left_half)
    & ?' z6 H+ \& M7 t& P/ N; `1 O, T
12.     right_half = merge_sort(right_half)0 a8 Q# ]7 C\" N' q; j
    
13. ' n\" ~* w$ n. g* r- C7 e
    
14.     # 合并左右两部分
    ) P* T; ?& u9 }3 e0 ^7 t4 i
15.     return merge(left_half, right_half)6 a, }& J; `2 S$ T$ Y+ [& U
    
16. + n7 z& f4 G/ i% y2 M2 V
    
17. def merge(left_half, right_half):* Z; g  z* D% s; N* C
    
18.     i = j = 0
    2 X1 |- K' F0 U
19.     merged = []) w! N$ ?. [3 e% v
    
20. 
    # `# i3 n\" ?; D\" F2 @( N3 @6 t
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中4 ^1 i0 L' l& C$ _. U! |: X8 q4 U
    
22.     while i < len(left_half) and j < len(right_half):
    1 F( s! M( ?8 e9 P
23.         if left_half[i] < right_half[j]:0 ?% ^. G; U9 ~  r
    
24.             merged.append(left_half[i])2 H9 S% p2 q5 g\" U4 l  b7 y7 r) {
    
25.             i += 1
    . x  U7 J1 C0 O, Q- e: f: B+ V' X
26.         else:
    0 \\" X8 j; X6 Q% `* n3 |% P  G
27.             merged.append(right_half[j])
    * h1 W& f3 b2 X# S0 t+ M0 K
28.             j += 1( {3 g- i  J$ b4 C4 r8 ~6 F6 b
    
29.   b6 l- `) b/ D% z
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    3 \! o( Q, `/ n$ d
31.     merged += left_half[i:]
    0 S% u7 L3 }6 Z3 A0 y+ }
32.     merged += right_half[j:]$ a9 }  d5 r5 B. h
    
33. 4 U, c8 D  g2 x
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   * Q6 i/ ?# l' m/ i8 j1 i! x- r
2.     if len(arr) <= 1:! E9 b4 @\" z9 X8 Q2 ~3 y+ R. u
   
3.         return arr7 c- C1 S+ f* f! a
   
4. 
   7 \7 z\" v* d0 R1 [0 ]( {
5.     # 将数组分成两个部分
   6 {! G8 [# Z# |! m% k9 m\" ^
6.     mid = len(arr) // 2
   8 }  r9 \7 I& N4 V\" J
7.     left_half = arr[:mid]
   ) U  X* y( i8 f$ v! E6 T7 g; I0 L' X
8.     right_half = arr[mid:]1 S; n5 \; Y: W8 Q, X) f4 G
   
9.   T: q* n% e5 X# X4 ~  s& J9 Y
   
10.     # 对左右两部分分别递归调用归并排序( ]& n4 G; N( ^' X7 J
    
11.     left_half = merge_sort(left_half)& O) Q0 L, k- q1 }5 Q
    
12.     right_half = merge_sort(right_half): d: Q0 b7 i8 a: f' P4 v7 D6 n
    
13. / x# T2 w; ]9 U* u+ q& u9 t
    
14.     # 合并左右两部分
    * C# c: X* k\" m+ y: W3 Y' |
15.     return merge(left_half, right_half)
    7 t; j: p# P* Q: g+ P  e* B
16. ```* Y( o( {, D\" h, p3 A
    
17. 
    8 P/ R' @' t- K1 W
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    5 l7 |  F9 A! i5 G0 a/ s) O* R

复制代码

merge() 函数

1. def merge(left_half, right_half):
   + W! @- U- x$ O* J# b- E' F
2.     i = j = 0( o* M4 c: q8 @4 V( z
   
3.     merged = []0 d9 v. O5 R- ?! n
   
4. 
   ; Q, p2 L; F4 e6 z; c# l  K2 J  A
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   9 o7 M9 a8 o: A! @3 O: v1 i
6.     while i < len(left_half) and j < len(right_half):3 t( E% N/ j; F
   
7.         if left_half[i] < right_half[j]:2 C) K! u1 k0 t9 w; s
   
8.             merged.append(left_half[i])
   * ^+ V# R9 J  j; f5 D4 _
9.             i += 1
   ' z. U' \) Y( u0 Y( O
10.         else:
    \" f8 Y* S* s; F) {1 O$ I1 S
11.             merged.append(right_half[j])% S0 J& R$ g7 f9 n2 U& s4 H\" g
    
12.             j += 1- s; G6 l4 j- I  ~( E
    
13. 
    8 R! p8 ~* H  |' [9 U
14.     # 将左右两部分中剩余的元素添加到 merged 中+ g$ E2 `, ?1 k0 S9 }+ n
    
15.     merged += left_half[i:]* h: L- f) N8 y
    
16.     merged += right_half[j:]
      }  B* c' M0 g8 q
17. 
    \" q4 U/ B7 ^+ i
18.     return merged# j% I+ ?0 N  c+ v3 V
    
19. ```. ^\" j& O7 H5 I2 Z+ q
    
20. 
    + a) m# F7 T) I+ ]3 T1 W
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
1 m9 [1 [2 i5 Q
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
! B+ H4 V" g. \8 x: f
/ H& y( k5 [7 j% o2 z% p$ y将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
/ u5 Q. G" m- E  g! b2 f, ~+ e
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
/ }/ a0 T, ?( O
. ]6 E! o: ^. h- v, f7 w5 _/ m& k9 {" Y合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

3 {& L# a# m7 ^" \2 }4 U7 U( }测试
& \( T& _8 ?5 z; y" q8 a在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   \" R/ n: a8 [& J; b; ^& `7 h4 m
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {
   4 C' p! Y% _& p9 O% O4 X/ p
2.     public static void main(String[] args) {
   & `0 t$ p0 O* D8 s( @
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   % j9 ~  ~: K3 H: Y3 O
4.         mergeSort(arr, 0, arr.length - 1);
   0 w1 e* O! C( ^
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   , e9 A3 U9 O( @
6.     }
   \" q+ q  K( Y1 B5 c) z
7. 5 r8 q- s0 q/ q% b6 A
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   5 w( z0 D: \7 R- y. m9 I
9.         if (left >= right) {- |' N- n8 ]\" [2 P% d
   
10.             return;
    6 H! V8 H) n0 `# [/ ~
11.         }( Z6 h+ z8 B% z6 Z
    
12. ! |; @, `\" ^\" {
    
13.         int mid = (left + right) / 2;/ {\" L2 k. J9 j4 p0 l8 K: w
    
14.         mergeSort(arr, left, mid);4 E3 }8 x( \2 j4 y
    
15.         mergeSort(arr, mid + 1, right);
    \" b7 s3 V# t+ A6 B2 Z$ L% a; `
16.         merge(arr, left, mid, right);
      @4 P; P! g2 K7 I
17.     }
    4 ]6 _( n! d5 N* f$ x8 r
18. 
    0 N) N5 H, L8 X; c. o/ a) G
19.     public static void merge(int[] arr, int left, int mid, int right) {$ r$ l2 z+ Y6 u# a) w( w
    
20.         int[] temp = new int[right - left + 1];4 s7 i6 ?7 v$ g3 Z
    
21.         int i = left, j = mid + 1, k = 0;\" v' K6 z/ ]0 \% ^! A+ ~
    
22. 
    8 G3 D3 t! Z4 i. _. r
23.         while (i <= mid && j <= right) {
    - s; T& X* A% i) ]+ s
24.             if (arr[i] < arr[j]) {6 ?$ S# ?* j! t: U0 }9 m
    
25.                 temp[k++] = arr[i++];) `; G; o/ d( I: y6 C. [' J/ K3 x
    
26.             } else {+ |\" t9 x\" ?2 T# z+ k. O
    
27.                 temp[k++] = arr[j++];1 j# J+ q& h1 ^0 C7 N
    
28.             }
    3 a/ y: `6 d2 V; Z
29.         }
    ; l, E# Q- W8 M2 M1 ^! s/ X
30. 
    \" W! ^' Y; Q+ N3 F6 Z% b7 i
31.         while (i <= mid) {
    + k9 @* P  b5 t; y
32.             temp[k++] = arr[i++];1 P0 ?/ i1 Q% }4 ^) y) S
    
33.         }
    ) u; H! S% Q- L  v0 z
34. 
    # G; j: I* t, X6 a
35.         while (j <= right) {
    ) G/ T0 y, f( S- b\" M% o
36.             temp[k++] = arr[j++];/ R: y  {' ^( z( l  E4 n5 G, I
    
37.         }
    . }' T, Y+ `8 t- d/ T& n
38. + c; o7 k! Q/ T1 E\" [7 y9 W) J
    
39.         for (int m = 0; m < temp.length; m++) {
    : P* f8 U8 J7 G7 ~( |
40.             arr[left + m] = temp[m];3 e$ e, c0 A& L. y4 b+ |: e0 x, W
    
41.         }
    9 T3 u  w. j( ~: C, n: X
42.     }
    \" o; `- U3 w9 d# c5 ?0 ~* ~! I
43. }

复制代码

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

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

9 ]6 h$ S( B8 f2 d9 L6 c8 h0 P1 UmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {! }9 |& ?- c% Q# o& f% ~
   
2.     if (left >= right) {
   \" i\" {# O5 B0 j7 N4 l
3.         return;  o! Y/ `9 Z) F' I# B
   
4.     }
   1 }- r/ n3 _8 ]8 ^$ [
5. $ u6 H6 q( j! t: d  X
   
6.     int mid = (left + right) / 2;
   6 ]$ W0 W! f7 l  Q\" T7 g
7.     mergeSort(arr, left, mid);
   7 K3 x& W- |6 e. N7 Y& H. e) N
8.     mergeSort(arr, mid + 1, right);
   ' x2 D- E/ h$ @& E3 t) _
9.     merge(arr, left, mid, right);
   ( x' x! B5 Y) S8 {
10. }
    \" e: @5 B) c' s  @3 m( ]- [( s0 i
11. 
      u$ F% L6 V6 g! s$ o( j

复制代码

这个函数使用递归的方式对数组进行排序。
9 J/ P" Z9 a+ C) v
3 c8 C3 C) o9 E2 o, @5 O! }* }/ p对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

! f6 O& r/ m/ D# k- V! ]) S# i最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
, p+ @; I& B- j1 A! S" o- S8 ?* t7 tmerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   ( e$ ~+ q$ i9 O; v* p) U
2.     int[] temp = new int[right - left + 1];& c, c\" y5 R+ |
   
3.     int i = left, j = mid + 1, k = 0;
   9 U4 I! U$ |0 ]( p
4. 
   , x8 ~1 {' c* S- Y! `\" y, l1 s
5.     while (i <= mid && j <= right) {
   0 H9 F6 {4 Q' W& p1 I) C
6.         if (arr[i] < arr[j]) {1 l, k* v1 Q! A\" x/ a/ \
   
7.             temp[k++] = arr[i++];! Y! ~4 x4 \. u1 X7 X
   
8.         } else {
   $ U* P1 g9 i/ Z, d$ E9 b
9.             temp[k++] = arr[j++];
   ' X8 W9 d8 O9 H. g. \
10.         }
    / T4 x. u8 a5 N; N
11.     }
    ' M( D' H\" ~* f/ D/ v4 M* H
12. 5 j\" [, y\" V6 v& m9 F% t\" h' A3 G
    
13.     while (i <= mid) {8 \! D8 H* }8 E+ y/ a
    
14.         temp[k++] = arr[i++];* R0 V# {8 @( @, Y\" \; `
    
15.     }
    0 ]. |8 Z, H$ h7 O
16. ; p4 d4 l& L' t  O! a! g) U
    
17.     while (j <= right) {
    % N( R2 w% n! m! n9 r& y% j
18.         temp[k++] = arr[j++];# j5 N+ t: x$ e
    
19.     }
      @( |7 H+ M* N. V
20. % S3 K9 p/ f: ~
    
21.     for (int m = 0; m < temp.length; m++) {
    ( E; X! h' ]% Q. Q2 ]
22.         arr[left + m] = temp[m];( _\" U* K- b6 X4 C
    
23.     }
    , F8 d8 C% h# f) f
24. }
    / _) h5 N4 L9 z1 p7 K+ @7 |& \

复制代码

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

合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
2 X; w$ ]9 K  h' W- w+ j8 l2 m- _
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
2 x) F$ B/ E* r* W1 t8 T
# H# E! o. B' U, J; }9 d这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

9 [! U- Q' S$ @" c3 z2 ?% b3 H! B




3 w, w7 a$ F) Y