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

2744557306

1 基础介绍
3 [9 [0 i  g. b3 P0 ]排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

. n+ h4 U, \5 {5 s5 Z以下是一些常见的排序算法：

: \3 F! s, [1 \6 U% T* x& i冒泡排序（Bubble Sort）
/ C  ^; J' S! f1 U, J
插入排序（Insertion Sort）
& \, v' }: N3 z. j  M& H+ v; C5 y
选择排序（Selection Sort）

! N! c, K2 g8 @; {" L1 S: L6 d归并排序（Merge Sort）
) i- [; u3 \. q: q* F; h5 E
5 c  t- [! w, H$ x8 e' ?5 l& n快速排序（Quick Sort）
) U6 ~4 |. K4 h5 s+ U8 Y
堆排序（Heap Sort）
5 B. q9 Q8 _* P$ B9 e
+ N! |  Z% @, h  C2 N; _% W( }8 k/ r一、基本介绍介绍
1.1 原理介绍
- q' @6 ^7 _# D归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

9 o: h$ B8 W/ U7 p* y) Q5 O归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
0 `) w0 n0 H. v* x4 l2 M1 H, W
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
9 v1 ^' J- H, I
  N6 u# X$ R, E; v/ x0 t; f$ E重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。
$ i3 w8 c3 u2 S' v1 p, d$ q
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

! H5 M/ |( G" U1 ]& t原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

0 g  O/ |# A1 o3 a首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
& S) ^* s* g$ M  y  Q# r- q
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

' ^( f7 w+ n# C0 \" {* N+ F对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
% X9 D/ W. a0 r6 r6 R) @
. p0 l. f# k6 c/ m7 O: F将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
; D& W3 w+ H/ m9 f, \* V6 t
1.2 复杂度
6 p$ |& i- _- Z9 m, b3 ~5 {归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

0 |& N* Y! O: M2 o$ {! o) h这个复杂度可以通过分治的思想来解释。

首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

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

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

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

1.3使用场景
$ X  H4 V% l: D# {% a6 s: f归并排序的应用场景比较广泛，主要适用于以下几种情况：

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

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
4 k( I# z* t& @! z2 B
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
. p( J3 U5 O" I9 B1 g0 B; h+ K
$ r+ s3 j9 d7 G' c/ [9 q对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

! {8 g; h; d+ }! ^9 [5 a总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
( ]! G% k0 m6 Z6 C( [
& w2 i& Z2 m; h  A* B) N1 X二、代码实现
2.1 Python 实现
' A0 y' {' \( y3 b2 n# C以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):8 v% I1 R8 u+ X' y+ G* |$ \6 F* _
   
2.     if len(arr) <= 1:( L% Q5 t3 w2 P( _  M1 f
   
3.         return arr5 x; ?  t) G$ o* n\" G3 g; E1 E
   
4. . [4 x\" o$ Z; o( T. i
   
5.     # 将数组分成两个部分4 H  {\" T  t* T9 a) |- A4 p
   
6.     mid = len(arr) // 2
   + m- ?- b1 d\" x# y  m$ e! c! `% Y
7.     left_half = arr[:mid]9 Y8 p9 j4 V\" x: z
   
8.     right_half = arr[mid:]9 n0 ?6 Y* g( X2 t1 q2 c\" A$ |2 r, l% y
   
9. . Z4 F0 M( ~- _\" ?& ~- u; r
   
10.     # 对左右两部分分别递归调用归并排序5 [' c4 S6 m9 j5 n
    
11.     left_half = merge_sort(left_half)
    + \3 F) L: y  W* S! x6 {8 `% Q
12.     right_half = merge_sort(right_half)
    7 c. k/ f1 F! n5 y9 i# X  y
13. 
    8 w\" a1 |$ Q( c; v) @: X
14.     # 合并左右两部分
    9 W8 b% ~, \4 Q& P  f6 C' E5 h% w
15.     return merge(left_half, right_half)
    % _7 k$ G' s* D9 n2 Z( r
16. 
    ' l8 @# [) [% M' @4 ?
17. def merge(left_half, right_half):( s: I) A+ r' _% Y& H
    
18.     i = j = 0& O8 Z\" `! }' B+ P; Z+ E! I% k2 i6 d
    
19.     merged = []3 o( ~  ?1 u' A2 s
    
20. 
      z- M4 }' n/ S3 a- P9 m, L
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    / h9 U+ s9 a: I3 C$ {
22.     while i < len(left_half) and j < len(right_half):
    0 N7 K, M& x7 U# \5 A7 T
23.         if left_half[i] < right_half[j]:
    0 Z- Z\" d( E! q( T* o* P# U
24.             merged.append(left_half[i])& |\" f  a( K* T; Y# J$ t
    
25.             i += 1
    8 }7 z9 @$ @/ l( ~8 m  k( u- z\" ^4 X
26.         else:
    5 m\" k0 h4 q! p  ]
27.             merged.append(right_half[j])4 c6 O$ G- d- d2 T+ F& G% b
    
28.             j += 1
    / M- }& }2 H  J: o2 C9 j
29. 
    3 e  r. f. U7 p0 \  u. u
30.     # 将左右两部分中剩余的元素添加到 merged 中; h# V6 ~- U$ e  n
    
31.     merged += left_half[i:]0 |4 ^! K% w\" |\" c* m+ ^6 `
    
32.     merged += right_half[j:]/ u: u5 n% Y0 T
    
33. 
    5 v% n$ w& W& Z' K2 ^% O0 K
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):& W; M! i8 G5 c0 `
   
2.     if len(arr) <= 1:
   , _6 ^7 R5 O* q# ^
3.         return arr  `) T3 e7 B' W' Y7 C
   
4. 
   - }( i$ u3 `) C0 w
5.     # 将数组分成两个部分
   0 j: `0 B% m8 i1 b$ i
6.     mid = len(arr) // 29 m! A  M; k, m+ D6 s
   
7.     left_half = arr[:mid]! R& h7 Q5 j. ^2 @0 _\" g: O
   
8.     right_half = arr[mid:]
   \" u2 P: H9 r! A8 e& M* o1 B, f
9. ) i# I! C# r/ z9 l+ S
   
10.     # 对左右两部分分别递归调用归并排序
    1 {* y+ X; A  Q/ K! f
11.     left_half = merge_sort(left_half)* |* J9 Z) D( w8 z7 F
    
12.     right_half = merge_sort(right_half)
    / H0 m, j: a* t7 Y, G
13. 9 L4 {: f9 l) J
    
14.     # 合并左右两部分
    1 r; }( \; r& j, ~# M8 y
15.     return merge(left_half, right_half); C0 _) U+ l/ Y! C+ `0 ?
    
16. ```9 |7 o3 T- e5 T3 y5 K
    
17. 
    9 s1 _( Y% K* w0 [2 `
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    2 h& x) |5 X' b+ t( a  `1 h/ C

复制代码

merge() 函数

1. def merge(left_half, right_half):$ t/ i6 c. T8 V
   
2.     i = j = 0' a) J1 o9 C, z/ u' u
   
3.     merged = []5 t( H4 C9 v. u3 p
   
4. 
   : t\" y8 N5 v; B: W% u* O- e. u
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   / }- P9 G6 v! F! d0 b* Z) o7 e
6.     while i < len(left_half) and j < len(right_half):# S- [2 m  A/ M2 Z
   
7.         if left_half[i] < right_half[j]:
   ) b/ s' c' W3 C% \4 q8 w$ N
8.             merged.append(left_half[i])# e% X* ^' P) U/ l8 z, E6 o* ]: `' y
   
9.             i += 1
   - r& K6 k3 ]9 l# _# s
10.         else:
    : r5 P. u9 R& p\" G0 {
11.             merged.append(right_half[j]); i( f& W9 c9 j( K
    
12.             j += 12 O' D+ Q. R8 B% k
    
13. 
    ; f7 `4 U# C6 \\" ]$ {5 v9 j: `, i
14.     # 将左右两部分中剩余的元素添加到 merged 中
    ) i0 O/ A7 {\" c: p  M6 [+ d
15.     merged += left_half[i:]4 Q+ N/ R0 |& A; q1 C9 {0 j
    
16.     merged += right_half[j:]
    % d9 \# [! J9 r1 q
17. 0 z) k* }, A2 {- G' y% e, K# K3 d
    
18.     return merged! V  b* N+ {/ c+ J\" z( b7 Q
    
19. ```
    - `* A6 Z: i  J# _. J; l
20. % R0 W1 H3 |6 O$ u
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
* h+ b4 ~, N! I# f5 O* z; g7 i
# k! j4 h# M2 Q9 j, C2 ~将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
3 l, z1 A0 m4 i) q/ a9 q
: i; ~2 I. L% D" F7 P; c. E% y) ^测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]3 R- @8 b6 O9 Q0 M8 ]. F
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
6 Y# A( `- W, I' r; j- V* k1 w
- k% |5 F% C6 U: m3 L2 _- E. M总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {+ o! V) f/ x6 A& {/ x7 |\" X, N
   
2.     public static void main(String[] args) {. N2 i2 i\" F& F\" V, n3 E
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   0 m* J! u8 t* \, `) t$ p
4.         mergeSort(arr, 0, arr.length - 1);
     W- Q! q! ?2 n1 g+ H3 f8 [+ a
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   6 a% D  l0 p: e; C1 k3 g
6.     }
   2 ^, w3 L. V! \. u# w  f% ~
7. 
   0 n$ H/ g& ]) H8 K- z7 C
8.     public static void mergeSort(int[] arr, int left, int right) {& Q! ^) t3 C. [6 i; ]\" @3 q
   
9.         if (left >= right) {* [( g6 B/ N* w5 U: k% P! G8 w* j
   
10.             return;& K* Y7 Y* F  C1 [: |
    
11.         }
    / R- F1 z) {- C9 A
12. 5 z' Q6 H  K1 d. a
    
13.         int mid = (left + right) / 2;. a; g! i8 a0 R\" n! c
    
14.         mergeSort(arr, left, mid);3 q7 @/ M7 I1 w1 `
    
15.         mergeSort(arr, mid + 1, right);4 F+ X/ v. R/ ?' A
    
16.         merge(arr, left, mid, right);3 q3 i- b3 i) r! [8 o) s4 T
    
17.     }# Y; s! M# p9 H
    
18. ) z* s\" n4 g. T# j2 L( l; I( W
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    ; C3 r0 z% b! m7 i2 P0 E
20.         int[] temp = new int[right - left + 1];
    ) @# j% n# d# v0 K7 i( z
21.         int i = left, j = mid + 1, k = 0;! _4 N) d8 ?2 Z! x7 e% p
    
22. 
    3 u+ @5 h, ^% S; V
23.         while (i <= mid && j <= right) {\" S# g( j9 @2 F% Q% N* j/ U1 l
    
24.             if (arr[i] < arr[j]) {
    , n* c8 k& ]* T/ ?- n) l
25.                 temp[k++] = arr[i++];
    \" \& l3 l' b9 T* v& g
26.             } else {
    - d( |2 j% L$ R; M& T
27.                 temp[k++] = arr[j++];# K4 G* [6 B! ^+ i$ r- X5 o; Y
    
28.             }* s8 E( d1 `. o  q5 `9 d
    
29.         }% N7 v5 q/ R8 |1 l5 z) J. ?' G
    
30. 
    & @: |# a: x: Z$ L/ M* F: L
31.         while (i <= mid) {) G6 `% `, j% M' E
    
32.             temp[k++] = arr[i++];
    8 ]) L% o  A/ Y, n
33.         }( }$ D+ A, U/ `+ O! N
    
34. 
    ; B, z9 A0 p9 A: o- m\" T( R
35.         while (j <= right) {' y5 ], ]. f& d\" V4 d
    
36.             temp[k++] = arr[j++];9 e/ V& C4 |) Q
    
37.         }9 e3 W# r# ]% f
    
38. * p- f, W% O- m, @/ ~
    
39.         for (int m = 0; m < temp.length; m++) {* u7 N: }( V( m
    
40.             arr[left + m] = temp[m];
    ( P6 H* a6 c4 j! \
41.         }3 l+ I% L8 s( Q
    
42.     }; U: A- ?$ N8 q& O8 v! K
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   - C  B! y, c) @0 c1 n\" u1 C
2.     if (left >= right) {. J6 T6 b6 K: B' v& o
   
3.         return;
   : i+ P2 D% T# y4 d: T- \# `$ L- x
4.     }\" I/ M3 h4 u: p& |1 j/ f7 W
   
5. 
   / e% o5 q\" h) U
6.     int mid = (left + right) / 2;
   0 O5 ]( |5 h9 p% f\" g1 S
7.     mergeSort(arr, left, mid);
   * E: l$ V( ~' W, J+ R
8.     mergeSort(arr, mid + 1, right);\" a& ]4 [: k# D' Q: V1 N3 M, }! N
   
9.     merge(arr, left, mid, right);( `! l- E  L  b6 J1 h9 P
   
10. }
    : P4 `$ X; r# O
11. 
    / P( `% {9 h# d8 V* x

复制代码

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

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

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

1. public static void merge(int[] arr, int left, int mid, int right) {
   1 o4 r* D0 Y\" x7 h7 V2 w
2.     int[] temp = new int[right - left + 1];
     Q$ l\" M/ M3 R6 [! v
3.     int i = left, j = mid + 1, k = 0;
   6 h8 b0 k  E% w$ A  u8 l& t
4. 
   * p# E2 ~1 _) y' ]3 q+ D
5.     while (i <= mid && j <= right) {# J, V5 a' h7 U5 D. b, S3 \0 ]
   
6.         if (arr[i] < arr[j]) {
   # P9 G- b, T( b! f
7.             temp[k++] = arr[i++];. V# V  ^9 h3 V0 F
   
8.         } else {9 P# i- f+ t+ o0 a
   
9.             temp[k++] = arr[j++];8 J% R1 z0 r0 q9 |3 D
   
10.         }# r  B: a( a7 |. c3 ?\" {* M
    
11.     }2 w2 n7 P1 Y3 g
    
12. 
    * m: Y5 J) c' n
13.     while (i <= mid) {5 Z& n9 P5 t6 Z+ w: a
    
14.         temp[k++] = arr[i++];# Y9 e8 o6 ?5 m: a( n\" e
    
15.     }1 F: h8 ?\" v6 Q7 l) U
    
16. 
    & d1 p4 I( P; \/ S* B. j
17.     while (j <= right) {3 q2 L! Q+ o) R2 q
    
18.         temp[k++] = arr[j++];- p8 E7 q& z9 T
    
19.     }' b% P2 p8 C) V5 V
    
20. - D$ d# O- Y9 A4 J2 b  @5 e
    
21.     for (int m = 0; m < temp.length; m++) {
    - Y/ d; d' d/ p& e0 ?) {# k
22.         arr[left + m] = temp[m];
    ! C7 q% Y$ |. c; h! S# I
23.     }# \$ K! a1 a5 B4 X6 o. V\" |
    
24. }
    * h1 \6 h\" ]$ v1 t6 o7 G- y

复制代码

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

合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
0 |' v; N, Z7 F6 z
5 d1 T  u2 G  @& o最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
% J9 W- t# z# `% H( F6 u* x* |
3 q6 d$ ^' c8 X. T. m这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
; z& o; ~9 q/ T$ t, x( i+ Q
0 Y/ l/ T- C9 k

) s6 ~" Z* E! `  v7 M# ~


' V- W2 ^+ G5 _1 \