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

2744557306

1 基础介绍
排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
" b7 b5 W* |8 o" d
以下是一些常见的排序算法：

冒泡排序（Bubble Sort）

插入排序（Insertion Sort）

" T1 d6 }& c- ?; U选择排序（Selection Sort）
; b1 @- p/ r( X$ e$ j8 v7 X1 T
归并排序（Merge Sort）

' `' Y( i0 g, r% `& V快速排序（Quick Sort）

. C- V3 D; [' M& T. q; p堆排序（Heap Sort）

一、基本介绍介绍
1.1 原理介绍
5 m) ?; E" w3 v. F/ i归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
1 X9 }% X* n6 t
8 I4 x! ^! z: E& l% r! |$ |2 Y归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
) t0 u) k1 {/ U( {# S' m  y  D
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
7 Z4 ]- T) J# l/ q
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
" J( A3 e. g8 c' v' ]8 U& _
, ?  A: L( k' s2 {/ ^) a. W合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
' B- l  O( i- O3 w2 Z7 h* K( N6 x
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

; A; k# |$ W7 P7 U; z) h* h" y' I* V比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
1 ^- K! m( y/ a2 d$ c  ^/ @
1 t8 |& m4 N3 |" ^( B3 P0 Q重复步骤 2，直到其中一个数组的元素全部放入 C 中。

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

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

7 W, {( t" w! ~0 i4 ?原理简单示例
1 ]4 v4 \; A! y2 W  S+ H以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
; ^$ P3 y' f- `( l
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。

! d( Y, w5 I: _5 ]) P首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
* T2 w$ X& M: Y( Q$ J
2 u  ^& I7 [9 _, {对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
' c3 E& e, t/ y4 T; W* P3 O
对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
: S( f4 \7 g% b
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。
" A2 Y1 R$ T: t8 p- r& k5 k* A
5 M' ?' _. H* ]8 u& M( v因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

  B# `  Y- l% N1.2 复杂度
) a+ p0 ]( A9 K) d归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
4 t/ J+ B* |* j" `3 B4 n, ]/ P
9 h4 M$ |; d7 `" U' h这个复杂度可以通过分治的思想来解释。

" ]- Z: |' u1 I( m2 C8 n9 P首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

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

归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

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

+ `0 z, ~) E% j) h, t! s* V5 i& {1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
2 t2 I& e0 w$ X1 n3 \2 b/ R
7 s* H% o( e- E- \, g/ D( Y8 n对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

3 q5 e. E2 J9 A% J$ M对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
! k8 a. h6 I/ f, J/ }/ R' I* y
: r3 ^- F. d- g6 d, a$ G. C对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
* x/ j: z9 [( l0 e
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

7 l* P8 j* t; @  |% t/ O总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

2 ]1 v0 {; k. O$ [, g9 ?, g; G二、代码实现
2.1 Python 实现
7 N  [& }8 p$ k以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   & X% W) N0 L8 ?. B2 M
2.     if len(arr) <= 1:
   ' X8 {6 I1 b8 D8 L1 H* v+ M5 [8 v
3.         return arr
   ' U, Z6 `% \1 C& m
4. 
   % i3 W$ t1 T. a9 ^8 T7 {
5.     # 将数组分成两个部分  h# \  S8 a9 \1 M+ k4 k. P5 ]
   
6.     mid = len(arr) // 2
   \" y\" C  `' ~9 r% [4 K( C
7.     left_half = arr[:mid]' c, ^9 p. V1 x( A7 K
   
8.     right_half = arr[mid:]
   + b) S( u/ k0 T+ D( V1 I. }3 Z
9. 
   ' N; A, v8 A3 Z1 @! G& }- F2 Z$ i2 i\" X
10.     # 对左右两部分分别递归调用归并排序2 K; R. t$ c: B& ]* y! U+ A' S
    
11.     left_half = merge_sort(left_half)
    ! o/ u0 d4 u0 }& F7 R3 L
12.     right_half = merge_sort(right_half), N% ?5 {7 x' e: o9 E  D
    
13. 
    - h) Q% D! w2 ]/ P
14.     # 合并左右两部分
    8 l. C+ S! }7 S. m! H: u1 b
15.     return merge(left_half, right_half)
    ) g$ @8 r, `6 ^/ c\" z
16. ! r( w1 O. f0 a) }2 [* C
    
17. def merge(left_half, right_half):
    * t# P* e: h0 I. f* [5 M( Y
18.     i = j = 0) s, B# q% A8 V# F1 |
    
19.     merged = []
    0 c: W9 Q; |5 f. ]7 f. Y
20. , ?1 G$ K# c& G7 d1 w
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    5 o  f0 `3 z$ M4 ?+ u& T- w
22.     while i < len(left_half) and j < len(right_half):
    - g6 j% K' H5 v9 u. q
23.         if left_half[i] < right_half[j]:/ i$ V$ k# ]\" }
    
24.             merged.append(left_half[i])
    ' k! s; E7 g. [. ?8 K4 k/ o6 n% Z
25.             i += 1& k5 F) v1 J1 D4 R$ p7 z6 O4 {( F
    
26.         else:
    1 ?; l/ L; P  Y$ j1 J+ K1 M
27.             merged.append(right_half[j])& @; k  _/ ]. D9 R/ J
    
28.             j += 1
    . [0 ]: E% b/ }1 X) i: ?5 ]
29. 
    1 M9 S, s\" M, S
30.     # 将左右两部分中剩余的元素添加到 merged 中4 U- Z$ ^! B& F7 q1 E7 Q
    
31.     merged += left_half[i:]1 W) w: A6 @$ R4 ]
    
32.     merged += right_half[j:]
    ; i( O- w, L. Y4 f: H- [- r
33. 
    ' O! F' @\" L4 J7 R
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   1 L0 s/ r6 T5 ]# f
2.     if len(arr) <= 1:5 {* E; `3 ~4 Y# U4 U' n
   
3.         return arr
   0 }) `7 q/ I5 G+ c3 \2 r6 G! u
4. 
   0 W# ]7 q7 f6 H, r' _( ]. y! B
5.     # 将数组分成两个部分
   5 y6 d9 |9 y/ m  u; x; R3 \
6.     mid = len(arr) // 2
   \" w% f# S/ Y8 [; ~& H\" R
7.     left_half = arr[:mid]: g/ N0 A5 y\" h$ [
   
8.     right_half = arr[mid:]- O- t9 T2 H7 r  a3 u
   
9. + Q* c% k. ^5 H. E' ]/ ^  ~* }
   
10.     # 对左右两部分分别递归调用归并排序7 I. q- o7 w; ]1 l! T% ~  T; W
    
11.     left_half = merge_sort(left_half)% `& R8 u4 N. Q+ H0 w8 Z8 W
    
12.     right_half = merge_sort(right_half)
    3 C+ z$ _$ M2 I& F' L3 F
13. 
    ( h! L3 v4 r$ z2 _8 A
14.     # 合并左右两部分  J' a  F) P9 k
    
15.     return merge(left_half, right_half)* x! [; k6 a  X$ g
    
16. ```
    4 G4 V- k5 L* H$ J& @
17. 5 `1 F0 o\" M0 l0 v3 N: n1 |
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    1 J( j3 }\" L$ G, L\" P8 G9 {' j9 d

复制代码

merge() 函数

1. def merge(left_half, right_half):8 I, X9 e& `7 [7 z5 p! m
   
2.     i = j = 0
   # ~/ C5 \4 x$ P, `# J' x) Y8 d
3.     merged = []% ~$ O2 I  f( |# F) i# A( _; ?
   
4. ) z- T6 n3 w9 a7 ]\" o9 x
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   \" W( P$ u: h; L3 [
6.     while i < len(left_half) and j < len(right_half):0 s  z) |# \- s  ]5 l5 {
   
7.         if left_half[i] < right_half[j]:
   4 ?: w9 q, P) `. \$ D& v
8.             merged.append(left_half[i])  d, o8 F, D+ H! t& U7 h9 m4 `
   
9.             i += 1( }# Z* K5 L2 b! |, T- S
   
10.         else:
    & m' {( j; `& ]3 o0 e% o
11.             merged.append(right_half[j])7 `( ^3 H$ h* ~\" a\" g
    
12.             j += 1
    1 ?, ]1 c7 m* H9 ^
13. 
    6 t6 M1 e* M* `: b: @
14.     # 将左右两部分中剩余的元素添加到 merged 中( E. A- {% m) M2 C/ ?
    
15.     merged += left_half[i:]2 n; N! Q/ z6 Q( H) Z/ G
    
16.     merged += right_half[j:]8 ^, f( I\" u\" a8 N, E
    
17. 
    ! z% ^3 v4 Q( a. Y9 Z
18.     return merged7 h: ~3 A1 f) U4 `* L) T
    
19. ```, N' Q* I; Y) ]9 y' K: }3 ^$ Q
    
20. \" t\" L4 u: Z* s5 b6 X1 E! n9 e
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

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

8 A# f' E- `2 m, _% q& s对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   4 o! f' ?2 U5 B* ]& M* _
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
, |2 A/ q6 {! h- E' j' Z1 P# E
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
+ F2 F) t: n4 [2.2Java实现

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

1. public class MergeSort {. G/ G9 u, U( h3 {1 S
   
2.     public static void main(String[] args) {
   / l7 d+ I+ q3 s
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   1 [/ L. U' T4 K. T
4.         mergeSort(arr, 0, arr.length - 1);
   ) X\" W7 f. E& P& c) c% v
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   * X% A. A% J6 T
6.     }( z: O( B* Q4 [: \
   
7. 
   9 Z  y' B3 B, Q  G5 \; ~
8.     public static void mergeSort(int[] arr, int left, int right) {
   : |2 {; Z: U- @6 J2 E4 ]8 J
9.         if (left >= right) {* u/ I* R9 {6 s% B  A6 t$ b
   
10.             return;# ~* ~& R! `- ]+ x8 O
    
11.         }
    4 q1 F9 C! E2 P9 l5 ^) L
12. 
      B3 S, e( F  G5 g, R7 ^) W6 m
13.         int mid = (left + right) / 2;
    9 @; m. \7 }6 O( T( q
14.         mergeSort(arr, left, mid);  ^* @* ~' Q' |( ]. {\" [$ ^
    
15.         mergeSort(arr, mid + 1, right);) W4 d; P. c8 ~. l6 q* x+ J6 U
    
16.         merge(arr, left, mid, right);
    ) M$ u, ^2 ~9 z0 L! q
17.     }
    5 [8 V7 @& o6 a' `% `  M4 {
18. 3 ^7 D+ X$ i\" A
    
19.     public static void merge(int[] arr, int left, int mid, int right) {* {' B6 g- V% b\" r
    
20.         int[] temp = new int[right - left + 1];
    2 d, g7 Y! l1 q
21.         int i = left, j = mid + 1, k = 0;
    + e7 D7 m! m\" J7 w% `5 c
22. 
    9 S/ w& p1 I: O\" t- p4 Q- r- y6 j
23.         while (i <= mid && j <= right) {; f6 A) |+ u% C9 ]% X6 B! O
    
24.             if (arr[i] < arr[j]) {  X# Z9 z/ V8 S+ s; O/ D
    
25.                 temp[k++] = arr[i++];
    ( _) E# o7 J\" s3 o
26.             } else {* F4 l\" B% }' d
    
27.                 temp[k++] = arr[j++];  G+ m1 K! P$ d$ m- G1 g
    
28.             }
    ) W2 u' r0 Z' O2 f
29.         }
    6 ?5 }5 r5 w7 @: O5 s
30. 
    6 k% R- \0 M; x, p+ t+ _2 g
31.         while (i <= mid) {8 X: M  U6 {8 z0 L
    
32.             temp[k++] = arr[i++];
    , K3 ?4 q) J: p( J. U$ u
33.         }
      G; j. D5 b! ?1 }\" l
34. 
    , y0 u/ Q\" n/ C* W' O
35.         while (j <= right) {: Q% u+ S6 d0 b9 [& `5 x; T' ]
    
36.             temp[k++] = arr[j++];
    % q0 ~\" x2 n. |1 W. x
37.         }
    9 [\" e/ ]! |- u6 i
38. : y. x4 N# u1 ~4 h
    
39.         for (int m = 0; m < temp.length; m++) {
    / }' y; J- v% x! H' A: k
40.             arr[left + m] = temp[m];1 j2 A6 c& @7 P- W  h8 S! r0 \# i6 |
    
41.         }: x) `& K( x) a2 J2 f5 R
    
42.     }4 u$ T5 N1 _& i2 j  c: r
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {( I( y0 f/ h$ f) `! u
   
2.     if (left >= right) {
   , Z  u\" r* B) B- K4 w5 e
3.         return;5 c0 y' G2 M+ y# m# E+ }
   
4.     }3 V6 ^: k' ?! j1 O
   
5. 3 N; [\" g\" |' L9 W0 c$ I
   
6.     int mid = (left + right) / 2;
   ( D  ^8 [- |6 B  J
7.     mergeSort(arr, left, mid);2 |1 V' d  |6 ?4 D\" Q1 O5 x\" n
   
8.     mergeSort(arr, mid + 1, right);2 M  R: e, Y5 \$ E' L6 R
   
9.     merge(arr, left, mid, right);3 v* D8 o+ ?& `* i8 H' f. z3 h
   
10. }6 X/ w1 \* S8 n7 l+ G
    
11. / p/ X# {8 n) ~2 R
    

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {* T' a' Z: B( d
   
2.     int[] temp = new int[right - left + 1];/ q) m* v, b\" e0 ^# t. `
   
3.     int i = left, j = mid + 1, k = 0;$ |' I; P$ a  B5 v5 J
   
4. 7 N5 F4 l1 m8 ]8 F
   
5.     while (i <= mid && j <= right) {
   ( {* K$ {3 D5 P3 c' D% K
6.         if (arr[i] < arr[j]) {3 `7 g: P\" K/ N& m& N: H
   
7.             temp[k++] = arr[i++];
   # Y( \% H; E  ~( Z& n
8.         } else {
   ! F0 N8 w7 ~) h/ S8 c- P7 x
9.             temp[k++] = arr[j++];+ J8 k% y( D( C) D5 f1 E
   
10.         }0 u% n( c& J6 y  S$ U
    
11.     }
    ) L0 C% K$ A. T9 ^2 ?1 u9 O
12. 
    \" N: J) v- g; \& {7 I! k1 w% s
13.     while (i <= mid) {
    ' Q# c) r0 i$ Q( D6 N- {4 S$ G1 j
14.         temp[k++] = arr[i++];
    & L3 E8 [& J! T\" ^* Y
15.     }& [) m$ A. M( w9 k3 g
    
16. 1 z; {. m6 S; q6 v# R! g- I
    
17.     while (j <= right) {
    4 `4 n  B4 s3 R\" g. m
18.         temp[k++] = arr[j++];7 o  N1 Q\" q& Y5 C9 r9 H# U
    
19.     }. z; X6 F. m2 V# F- [
    
20. / Z& {; [) u, r( x/ o) K& U6 d
    
21.     for (int m = 0; m < temp.length; m++) {
    6 `3 j4 L' _# Z5 f
22.         arr[left + m] = temp[m];; F; w7 t, X5 Z! {8 h# B
    
23.     }
    / q- r9 D% e  a& d3 A9 M
24. }
    5 p\" ~) S6 }5 @. T

复制代码

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

+ E) X0 ^! J3 v( M, {( z) g合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
5 n9 w9 v1 S; M1 [# \& j0 N
! t5 V  q1 _& i* G6 I4 z最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
& X7 x5 ^) @3 {- W. {& u
7 X) z6 k" g# l需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
2 _4 \5 ^: B, F+ A
4 q. ?! a6 W" w5 z$ }  _这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
& r5 c7 d5 T7 i& ?6 l



8 j: P% ~- i2 z$ K/ w- a

* A* C- B. g8 e% U! n