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

2744557306

1 基础介绍
6 }3 H1 q& M6 h7 r" S. `  A排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

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

冒泡排序（Bubble Sort）
0 ?) T8 u' U& R) `5 L" y3 P$ A, {5 c
插入排序（Insertion Sort）

选择排序（Selection Sort）

归并排序（Merge Sort）

/ X3 D$ P  m# h& W+ B快速排序（Quick Sort）

& ?* q& q/ K- C* [* O: q堆排序（Heap Sort）

一、基本介绍介绍
1.1 原理介绍
4 ^! o; Q9 V1 K归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
* x( ^* r7 b, K5 b3 W$ w
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

+ S7 n: q# f5 Z: b! S8 |& u分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
1 _& M; ^9 J; `. R# m+ N
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
3 V/ z9 {. J+ `& Y
/ v$ F; _. R% N  M) w) R合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

5 X2 n7 E; Q3 }& n. E' q定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
/ F, h. K) ]( K) V$ i! F) Z  ]
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
) j+ \' K& F: @9 k+ @
* a. {) Q) I0 i0 q重复步骤 2，直到其中一个数组的元素全部放入 C 中。
7 [7 n; b9 {" M& L* t1 `6 K* i+ R" x
. ~0 a* v7 \) x9 h4 h+ r+ Y1 p( Q& ^将另一个数组中剩余的元素放入 C 中。

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

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

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
, V2 |6 R% E& A8 c
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

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

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

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
  ^1 O* J! r7 j  N* t4 P
0 d& B1 x# }5 o0 @将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
( k. s2 X  I' t& B* Z. z- b
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
! M8 Q$ j7 H* T+ l
8 N, w% }) E5 @' W5 Z3 d$ _1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

这个复杂度可以通过分治的思想来解释。

- Y1 r9 g0 Q; d$ g4 P首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
8 I( ^; Y7 W: G- r0 B) d  ]8 s
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
$ j4 ?; M! x' [8 A' i% a
( v- v9 r0 P+ d9 ]% B8 T+ u6 l归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
; W, a5 g' W% S5 n, u7 c$ U( C
这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

5 ^5 \! ^1 {) V5 L9 W( b! t" o5 I对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

& S* l" u' N6 E5 B, |1 L对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

# u& z5 C2 P6 k) O+ k8 p" [对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

. p: b! P( Q9 p$ J% h对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
! O& v  b0 i! |- o* [, }
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

: o% @8 [" X" w( U总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
; t9 u/ q4 H! L2.1 Python 实现
& |9 L/ v2 u$ D. Q) s以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   ( \: `& m, c\" _\" [. w( e; P6 e
2.     if len(arr) <= 1:& u4 T/ `  F+ S# }
   
3.         return arr
     c- H8 ?8 a9 h/ D' ^) [( |( u
4. 
   # r* H- i% }) i\" u) q0 a
5.     # 将数组分成两个部分
   3 N% v+ E3 _4 a) O; k# K  O
6.     mid = len(arr) // 2
   \" L' ?$ x/ _' M8 I- x
7.     left_half = arr[:mid]3 F5 b# M$ V5 {& \# q* A. K
   
8.     right_half = arr[mid:]2 o( o7 u# ^! ~; b' z2 ^2 ~2 ]1 U
   
9. . `2 s: p& y- F\" z. m
   
10.     # 对左右两部分分别递归调用归并排序2 g$ n; Y! ?2 d
    
11.     left_half = merge_sort(left_half)4 B! Z4 W6 Z* O9 C
    
12.     right_half = merge_sort(right_half)) \, X1 [5 j8 q$ r# \5 _
    
13. 
    ! ~* F- Q( f* e- r( ~4 H
14.     # 合并左右两部分
    1 v\" Z' `\" y' ]: A$ Z
15.     return merge(left_half, right_half)6 w, x6 v9 \( U' V: @/ f: |: U
    
16.   i8 R/ [8 I1 }$ _* T. K! _1 d, t
    
17. def merge(left_half, right_half):* p: {$ C/ ^3 h  l: t\" ]4 J; W1 a
    
18.     i = j = 0
    3 x2 J0 g: `/ x6 R# a1 k% i
19.     merged = []+ P; {% [4 m! R. P% A. E6 N+ U. a
    
20. 
    , ^* J/ D$ ]6 ^3 D: Z! z* h\" W
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    8 a' c' _# W7 A) F
22.     while i < len(left_half) and j < len(right_half):
    0 r. Z( b- T* j\" u  |9 B2 a( F! @
23.         if left_half[i] < right_half[j]:% {# S$ g8 |8 ?8 @2 ^% ]9 B( E  M
    
24.             merged.append(left_half[i])
      i1 F! Q# B: Q- F3 I4 `; e
25.             i += 1
    1 n( B( v4 U! C. E% }) e
26.         else:9 ^, K* A) ]2 i$ }
    
27.             merged.append(right_half[j])3 @& W7 U; v% q- n. ]/ x
    
28.             j += 1. `+ Q; R' `% u3 M
    
29. 2 p' f9 A/ e0 Y
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    / I) f$ V2 B/ t! n# L5 v8 {
31.     merged += left_half[i:]: @0 P  F* D1 X& a4 `
    
32.     merged += right_half[j:]
    ) L$ S. {\" j- M, i8 B2 m
33. 9 E) @. F3 `* r. t- R  H
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   & K  u4 q3 |; ^5 d4 D
2.     if len(arr) <= 1:
   3 h; V% p+ ^& k1 ?. X/ z
3.         return arr  s* t6 R! N. Z; o
   
4.   a9 r* {1 W- j
   
5.     # 将数组分成两个部分
   + c7 U2 T$ h' M
6.     mid = len(arr) // 2
   & d6 a0 u1 D5 M
7.     left_half = arr[:mid]\" }- ^  w$ v6 {7 W, ?- z( ^' g
   
8.     right_half = arr[mid:]; e% ~& }) X/ b
   
9. # n0 b5 ]6 M9 Z: ^  F) Q
   
10.     # 对左右两部分分别递归调用归并排序, V% w  T, z+ c6 M8 I( H+ a
    
11.     left_half = merge_sort(left_half)
    $ v6 {5 j5 D! \+ r3 e
12.     right_half = merge_sort(right_half), |+ h$ X. K+ Q6 H! Q0 D\" l& x  e
    
13. 1 q2 ^/ ?% c( w% `- ?
    
14.     # 合并左右两部分
    2 g9 ]# [& j: A- X9 Z  E( @% V5 x) ]! K
15.     return merge(left_half, right_half)\" `' _: \/ v2 k2 h& e
    
16. ```
    / d1 I# z8 t# E4 ?, e9 i\" z! l0 @
17. ; ]' E5 ~# I' r; ~, z) j# S. z
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。5 [2 i7 _0 t7 N$ J* E2 d
    

复制代码

merge() 函数

1. def merge(left_half, right_half):$ \4 Z! v5 V& c3 u, }
   
2.     i = j = 0* e! t: C8 D5 D: z7 T# y7 H
   
3.     merged = []
   & v\" {# o  T: w2 L
4. 
   2 c' F+ w$ p! n
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中7 N$ c0 g. g: y3 B7 ~
   
6.     while i < len(left_half) and j < len(right_half):
   $ e3 z! R+ V: G% r6 d# S
7.         if left_half[i] < right_half[j]:/ ]. ^- J- w4 P$ K$ D% x
   
8.             merged.append(left_half[i])
   \" H\" J' \* J  z4 q2 U
9.             i += 1
   6 o  t: E% x8 Q* p
10.         else:
    - K\" x- F* S( u; F
11.             merged.append(right_half[j])
    0 G. y( H6 s0 F3 Y
12.             j += 1
    & h1 u- \0 u, L8 B0 X
13. . b8 h7 Z) Z. q# e. d& C
    
14.     # 将左右两部分中剩余的元素添加到 merged 中
    % A2 d- r% s  M8 b( `0 A7 Y5 ]
15.     merged += left_half[i:]  B\" L- H* C% {% [+ }0 v; e3 P
    
16.     merged += right_half[j:]' {7 w% p. P! v% q\" b/ i$ n
    
17. # J\" Y: v* Z5 ?% F, H
    
18.     return merged
    ( H& o, }4 e8 _
19. ```
    * N: i$ F3 u% g
20. 
    ) i5 U  m) d4 Y. j4 Y6 {! U
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
) m7 k( r0 a& r6 H
+ q) M4 t. E" C  T判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
9 A) T/ a3 g; }* Q% Y* P
; R0 T* ?6 F1 D8 t2 Y1 C. `; s将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。
3 o, K) H7 O, i6 V6 ]6 v
对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
8 H5 Y& C: o, _7 W0 R& n
1 `8 ^, }' Q1 H测试
0 \; D: T6 h7 ]  ?在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   0 K/ v9 S) a7 |5 @+ z
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
+ H, F2 C% E; s; _: j
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
7 ~1 M4 c- U; t- p) I9 |2.2Java实现

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

1. public class MergeSort {0 G7 v% m- k& P1 {, p; L  w5 v
   
2.     public static void main(String[] args) {( L' L2 n  x8 n
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   & `0 d8 T6 H5 b& V6 ?
4.         mergeSort(arr, 0, arr.length - 1);
   2 u% G! U6 J2 I
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   ( U& M- S, |' K7 w( ]\" M
6.     }% f6 H, H$ x0 E2 B) v+ {
   
7. / Y. G\" L3 H; X
   
8.     public static void mergeSort(int[] arr, int left, int right) {) @, V0 {( o5 h  a/ y0 J5 C$ B
   
9.         if (left >= right) {
   $ h! g! D\" t* F8 G- B\" S
10.             return;1 @$ }/ ]\" p+ ?1 D6 R$ b! r
    
11.         }
    + h- f- T$ g. ]: `* s% U0 J, O2 x
12. 
    7 m' c& I3 I: c6 |8 V; A
13.         int mid = (left + right) / 2;# ?8 l5 U! }# r8 ]
    
14.         mergeSort(arr, left, mid);
    & ~% D$ P1 m$ s9 I! X% }- |4 [; k
15.         mergeSort(arr, mid + 1, right);
    6 W3 w4 Y; ], @
16.         merge(arr, left, mid, right);. ]9 Z3 Q/ E: h, F! ]( R$ x: u
    
17.     }
    8 L/ d4 i) \\" }- w& m
18. 7 R1 v$ F6 E: M( d/ c( s
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    7 g. X% I; o! C
20.         int[] temp = new int[right - left + 1];
    + W0 W! b\" |: L; O! Z
21.         int i = left, j = mid + 1, k = 0;
    2 w% A1 L5 W\" e7 X6 i- P
22. 
    , ~9 b9 S9 H5 a1 b( @  v8 h
23.         while (i <= mid && j <= right) {
    . a5 j! t5 J) n) |
24.             if (arr[i] < arr[j]) {2 R: x, y0 q) J: Y- m3 z* P! R8 V
    
25.                 temp[k++] = arr[i++];# U4 M! n7 C, p/ v6 @
    
26.             } else {
    \" t! y+ C7 H4 Q. b) e9 R7 [
27.                 temp[k++] = arr[j++];
    % A; T2 a1 |( ^8 [9 g
28.             }
    . W) s; R9 D) j5 k4 r& t1 `  t
29.         }, `3 r0 X4 Z/ k2 K5 s
    
30. # u3 |) ?0 E  S7 G9 D
    
31.         while (i <= mid) {
      z( O\" }- P2 S! T- H4 D8 X! a+ I+ h
32.             temp[k++] = arr[i++];
    ! p( n8 v- ?! V1 b; E+ ]
33.         }
    1 X- {8 l+ V$ @# ?\" m
34. ' G8 o\" b& f3 A
    
35.         while (j <= right) {
    1 {) z. R4 E, f* K2 ~. \0 z
36.             temp[k++] = arr[j++];
    ( k. ]& j9 ]6 t\" B* c/ s8 `
37.         }2 |1 d. V+ m3 O# V# H
    
38. 
    8 E! e3 a! H. {
39.         for (int m = 0; m < temp.length; m++) {
    + s, a0 e2 u' L. D
40.             arr[left + m] = temp[m];0 R  l; z1 R* ?, W8 G* T6 x2 r
    
41.         }+ w% T$ h\" M/ ]
    
42.     }
    ) p  S4 W\" I/ O7 `/ q
43. }

复制代码

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

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

2 Q1 a+ v% F! W5 W9 d$ z* y3 q- qmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {) a: l% H' H\" K! @8 Z, L
   
2.     if (left >= right) {
   \" A( _% J: H( l& C# t
3.         return;! @5 X9 [& D0 e# K; K7 h( t# t. K
   
4.     }
   5 F\" E5 R3 g; _% H; k3 Y( M  f3 S
5. $ l- |$ F1 J' V* L  a' D
   
6.     int mid = (left + right) / 2;
   ! m2 R8 w3 ^( [# n& i% p  r
7.     mergeSort(arr, left, mid);
   3 t/ i( r+ |7 A/ g! j1 d4 v( j/ G2 f
8.     mergeSort(arr, mid + 1, right);
   5 @! @! ?! ^- [, L; S
9.     merge(arr, left, mid, right);4 r3 e. \3 d1 h6 v. Q7 z2 U4 j+ J4 `
   
10. }+ H2 s: P6 M7 M$ v# `' w5 i
    
11. 6 Q; G5 q* b/ v1 v) h
    

复制代码

这个函数使用递归的方式对数组进行排序。
' y6 O0 \8 w; B8 Q6 K8 u
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

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

1. public static void merge(int[] arr, int left, int mid, int right) {! A9 N- G/ P- }8 X0 e
   
2.     int[] temp = new int[right - left + 1];/ H: b! j3 J/ S\" V. U7 `
   
3.     int i = left, j = mid + 1, k = 0;
   - w) ~& M6 j' ]3 ~. D  @
4. - L& }: H( [( {
   
5.     while (i <= mid && j <= right) {
   ( L' ~9 ^7 u. k3 \
6.         if (arr[i] < arr[j]) {5 b# S' x: u* L- O7 R4 K5 S4 h
   
7.             temp[k++] = arr[i++];6 b: `4 N9 `# P
   
8.         } else {' D\" o( O: h! o
   
9.             temp[k++] = arr[j++];+ b& I3 _\" R4 l) T0 i% @
   
10.         }1 {4 U$ b* s/ K. |; z
    
11.     }
    9 l9 n- J  y/ @/ {% f0 D) z
12. , D# }! R* G  n' A' V! R/ `
    
13.     while (i <= mid) {% F; S$ X* n, H! f$ }\" \& G( M+ l
    
14.         temp[k++] = arr[i++];' C6 s0 H4 n' o5 H
    
15.     }% C+ Y6 u0 v0 C- y( \! T% U
    
16. 
    / q, ^; J9 \+ W, G/ C\" l5 P9 E
17.     while (j <= right) {
    - c- p- L9 N+ i  v
18.         temp[k++] = arr[j++];
    0 s+ ~- q\" W: k4 K
19.     }
    7 W4 O  X6 P$ L/ s3 A8 k
20. 
    3 ]) l0 x/ N8 V$ |# b8 p
21.     for (int m = 0; m < temp.length; m++) {
    & @1 I2 Z' N. D- _2 j. S
22.         arr[left + m] = temp[m];$ Y9 \& [- ~$ j7 B; N
    
23.     }
    9 S3 Q& V3 j1 {, S; R& V) k
24. }0 G& z% @- G0 K, |5 X0 p6 ~
    

复制代码

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

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

" P  Z. w0 }; q4 S" D% a最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
' z/ l" f0 ?$ f* n( R+ Y6 u' B' w
1 K/ r& k  ~$ L* m0 t8 L需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
0 ~  c( _9 S5 F
6 R2 p: {& \3 K* ]) W& q+ A这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。


1 A, k: O. [4 V/ n- M8 A. |
0 @3 `! ~( c8 C& ]/ L
6 E  s* R) T! X5 M
* I1 t8 ]! s; ]5 a
) d+ @! Z, [/ S7 R2 E6 y  Q, B: s