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

2744557306

1 基础介绍
; c* c! i# t7 @$ _) Y& N排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

以下是一些常见的排序算法：
8 X% l- I/ g) @: z; [
冒泡排序（Bubble Sort）
' L6 F' d$ d' S% b6 L
插入排序（Insertion Sort）

3 P: M& ?2 P* J/ Q4 s选择排序（Selection Sort）
: Q3 Z7 d1 i/ ~- t
归并排序（Merge Sort）
0 ]9 l( j/ f1 d" b: g/ G
快速排序（Quick Sort）
) [% S1 ?0 i0 v; ?5 r% ~
9 W+ \& w) l+ v  S9 K堆排序（Heap Sort）
9 d' K3 {5 I: F# {5 h
一、基本介绍介绍
1.1 原理介绍
1 o; h! u* h5 r1 W/ F归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

0 M0 i3 g/ H* A7 I# ^& X合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

1 G7 Z( [) u7 {5 b合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
7 O" S( y7 B! p( r. ]- |, Q
) ]/ a) C+ }+ [* K. R, I7 F定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
# N6 T+ l! E/ m6 W) v. g' ?' e
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
- o2 `/ U. o. O4 D6 I( k$ b
1 k: p1 b3 \0 j% _5 s5 X将另一个数组中剩余的元素放入 C 中。
$ q4 p8 e9 A. x; f, l4 I) q
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

+ Z- ?* Y3 U+ X) `原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
* N$ r- x  Z7 Q3 z: {. y  J
对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
8 Y8 k9 A6 [6 e$ V$ L" r
对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

$ r  T9 T/ y" P6 m2 k' r接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。

0 `/ J# g1 _7 k8 K  F( E' z因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
. @( n% @" O/ E& [, S* R# X
1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
! u0 k* J1 i" [$ h" z9 \
这个复杂度可以通过分治的思想来解释。
2 c# {5 s, ~3 X2 W- Z; F
! S  w) w% ?& v( |8 U/ T4 @, M. T0 A首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。

每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
3 y  `2 G, U7 M. n8 S
) H- G% z7 L/ {+ ~0 x归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
* g& O# w% [; {. x4 b
3 p3 {7 O; P/ r! _' T这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

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

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

# X. i: k2 K, A- _对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
8 R5 Z) l5 R6 \. n. H+ h: n
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
! U4 b8 Y% h7 n, ^+ ?: o8 p
9 F  E' T$ s1 z0 n% K5 w' o对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
) ]: {4 [# @- y( U
- r0 J" {& }4 y6 c, o总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
- I! |( D/ B* Q: s4 M
二、代码实现
2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   . u5 ]# K. B# W6 s) `; J
2.     if len(arr) <= 1:4 f( }( [; ~3 w/ |8 F
   
3.         return arr
   \" r) w1 E) b' T& c6 G+ H
4. 
   / x& |! K/ t8 W% V) j$ m  Q+ d& d
5.     # 将数组分成两个部分
   / ~4 ~, A: ~  ]; F* I
6.     mid = len(arr) // 2; ?% e9 t1 r3 H# z0 _8 V\" P9 [
   
7.     left_half = arr[:mid]4 P# |) H# Y! h. A( s7 i+ U
   
8.     right_half = arr[mid:]- q$ \\" A8 g4 @5 C$ v/ r) ^2 _# ?& V
   
9. 
   - ~6 T6 z. y* O( S, `
10.     # 对左右两部分分别递归调用归并排序) k5 A2 q4 S0 U; c7 S6 H- E
    
11.     left_half = merge_sort(left_half)! ~! j6 a4 q\" ~5 C
    
12.     right_half = merge_sort(right_half)
    $ ?% d\" k) T1 R9 z
13. 
    6 j8 U# s4 {0 ]
14.     # 合并左右两部分# u  P* Z( g% Y8 \2 Y* W
    
15.     return merge(left_half, right_half)1 X0 `) b$ j0 z  a2 C
    
16. ( C1 w6 t2 ]3 {. W) p
    
17. def merge(left_half, right_half):/ _1 I0 y& f8 D) |6 F
    
18.     i = j = 0
    6 g* k( b+ I. U$ H6 \
19.     merged = []
    * B5 ~0 a' I- t+ u# T5 ~
20. 0 f! t( q6 V, W( d7 z- _5 P
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中* j7 N; U8 N& V4 _8 P# k4 W
    
22.     while i < len(left_half) and j < len(right_half):5 a) X4 M' f! W9 |( b* P* l9 ]
    
23.         if left_half[i] < right_half[j]:: c% H/ u& L\" |5 U, \
    
24.             merged.append(left_half[i])
    . J7 F\" w1 h0 S, M
25.             i += 19 X* @$ |1 A- @+ u0 G
    
26.         else:
      f! ^( a, h' f
27.             merged.append(right_half[j])/ E( |/ ?# z5 D# Y- @# H
    
28.             j += 1  G! `# D1 h) S% F% q. n
    
29. $ Z) w\" z6 ]) }* T6 d/ n
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    \" b- Q% L; _5 Y1 J
31.     merged += left_half[i:]
      f$ u) Q1 L9 M
32.     merged += right_half[j:]3 L8 L' Z+ s; _6 d
    
33. 
    2 [) [+ M; Q7 V8 B2 ?; y
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   2 P0 h. m$ m; z0 [. ^
2.     if len(arr) <= 1:
   * Z- d( U8 j2 c. q: g/ Y
3.         return arr, W' M- T4 {7 _  b% V
   
4. ' f6 c- P7 U, `; U+ r) e
   
5.     # 将数组分成两个部分3 ?0 q& P\" p* t. n5 K# A  @  r6 B
   
6.     mid = len(arr) // 2* L5 c8 V\" N# J  R( e' {/ k
   
7.     left_half = arr[:mid]- U! T4 \5 s7 w) S! f2 a- n
   
8.     right_half = arr[mid:]# U) h) m) P$ d0 c  j
   
9. $ c  R4 b5 Q: t# ~2 p% d. L
   
10.     # 对左右两部分分别递归调用归并排序+ y, [0 E9 w9 b8 G
    
11.     left_half = merge_sort(left_half)
    2 d4 v1 u- j1 {  R6 P
12.     right_half = merge_sort(right_half)
    ( U- ^) o/ S2 f2 M8 F6 S
13.   b- m* t) Q) O8 d' m3 E
    
14.     # 合并左右两部分
    5 J  w: A, U5 C- \\" C\" ]
15.     return merge(left_half, right_half)3 q# _* u; ?+ M5 q: E; H4 R: e9 x
    
16. ```
    ( M9 V% _0 I5 M9 D0 e1 ]
17. : T\" h6 W, s  O$ r8 E$ N
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    / |- c- d- s  m' ^$ r\" w3 s5 b- n

复制代码

merge() 函数

1. def merge(left_half, right_half):- l. r* L1 D8 q: {
   
2.     i = j = 0; `8 T' f2 _. _0 o\" L9 Y( R6 G* J+ e+ i
   
3.     merged = []) f/ ~. A: w% v2 V\" P, d
   
4. 
   9 |# h- _$ ]5 f6 \7 q
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   7 O+ I7 ]; k: D9 x% {5 j) t8 @# u
6.     while i < len(left_half) and j < len(right_half):/ K' \3 n* L: {- n2 D) `/ v
   
7.         if left_half[i] < right_half[j]:+ D  G6 h: Z0 I7 \  m# U
   
8.             merged.append(left_half[i])
   $ J+ K0 {- h: C1 j2 H7 B
9.             i += 1& V' F9 e9 `3 a/ _, \: K7 k
   
10.         else:' k6 S' [8 Z7 R  G5 Q6 ^
    
11.             merged.append(right_half[j])
    $ S' U6 B6 f  [# {\" ~3 [
12.             j += 1
    6 L4 r, ~3 [% w/ m: T
13. ' h\" H. {8 N+ {# Q4 P+ d$ X3 v7 i
    
14.     # 将左右两部分中剩余的元素添加到 merged 中  e3 |; U8 V2 [# ]0 z
    
15.     merged += left_half[i:]
    4 o- G+ m8 o1 p. Z3 D4 l\" t: Z, M
16.     merged += right_half[j:]. [2 j5 B, g, N\" L3 o\" n
    
17. 
    0 [3 `3 t: V2 l
18.     return merged( w6 ?2 k7 V* ^, F
    
19. ```
    7 p1 f+ X1 S& W6 a, U+ P, j2 L2 O
20. 
    8 N; @3 b6 i! C# F
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
5 |) ^! C1 K1 J, f
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

! m3 \/ a" `" `  G# q, a: ~; j将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

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

9 V/ b% ^% p$ f9 F合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

0 |$ q9 f' s& B0 [+ Q( k3 l测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]3 G. y\" f3 {, ~! Z: y
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
( `' U$ l8 B/ v5 X$ u
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
2.2Java实现

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

1. public class MergeSort {# B8 v1 O( `\" P  R, v/ ?, h8 K
   
2.     public static void main(String[] args) {
   - V\" Z. [) x5 m1 E
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};. O: _, P8 I1 P1 T2 o# W) ^
   
4.         mergeSort(arr, 0, arr.length - 1);3 u% F3 n) p5 |' n
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   1 t1 i# M- e3 t% C* Q; w4 X8 ~
6.     }
   9 q3 B( ~; d5 D/ u
7. 
   7 i$ y% H% ?$ s! L
8.     public static void mergeSort(int[] arr, int left, int right) {
   $ Y1 a9 h+ w; j6 l* D5 |6 b9 Z
9.         if (left >= right) {
   + o' K9 q: J8 [( [  o) ]% q, C8 S
10.             return;! ?6 A& a8 {% t$ {; @5 B
    
11.         }\" X' g5 z- a4 ~, q. u# w5 Q
    
12. 7 g( L8 H\" d# {& a2 Y' ^, P
    
13.         int mid = (left + right) / 2;
    ' d% ?7 P0 u/ d6 O/ c( y- V& p\" P
14.         mergeSort(arr, left, mid);3 E( d# L2 j4 k( y
    
15.         mergeSort(arr, mid + 1, right);
    ) c\" l: F' f. Q8 o) x  V3 F
16.         merge(arr, left, mid, right);/ {\" K* h, R* J; y% r
    
17.     }
    ( D( g) Z# G2 D4 a\" z
18. 
    $ F0 P) \! ]; _8 I* s! D3 r
19.     public static void merge(int[] arr, int left, int mid, int right) {
    \" r, ~& L6 D( Q/ k7 k. L. l
20.         int[] temp = new int[right - left + 1];
    6 S4 Q# T0 M& u% k; i' `6 h/ `
21.         int i = left, j = mid + 1, k = 0;# n, \0 O9 ?% x! n4 S9 d
    
22. 
    + N\" I( ]! o8 N. \6 Y- s
23.         while (i <= mid && j <= right) {9 p\" [2 Q+ `\" v: [- a( ?
    
24.             if (arr[i] < arr[j]) {
    ) Y6 x/ V5 z7 j\" J# R% X1 y
25.                 temp[k++] = arr[i++];+ \; Y' S  w) ^8 z8 f
    
26.             } else {
      O1 T7 _1 p: c  }6 Q6 m  f8 Y
27.                 temp[k++] = arr[j++];
      P  A! ?4 J! L3 O& G
28.             }2 ~9 ^$ M  L0 k! f
    
29.         }
    ' f9 q  N$ }1 z+ U/ i
30. 7 _% I! \. p( D: B0 s
    
31.         while (i <= mid) {9 a8 y. n; k4 I3 L4 ^
    
32.             temp[k++] = arr[i++];6 p5 i, R# L. o! U3 J8 h
    
33.         }1 F) o9 H+ n1 U& x
    
34. 
    8 G\" q7 z) H, j$ K2 j
35.         while (j <= right) {: |# ]1 B3 P$ h( ~& J
    
36.             temp[k++] = arr[j++];
    + a/ z* Z7 j\" @+ i$ E
37.         }
    ) K7 e\" f+ W  o+ Y/ l/ \# _
38. 
    6 }# x! u% N& V- z( m
39.         for (int m = 0; m < temp.length; m++) {, V; ]+ M/ R# O5 A
    
40.             arr[left + m] = temp[m];' K5 U/ i\" S# C
    
41.         }* ?& D9 x+ p! U
    
42.     }
    1 Q( g; _* G, ?
43. }

复制代码

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

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

6 m2 n! }5 E# M$ Y. q, N, P! QmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {% R% I( y: v2 G0 ^9 b* J6 a& P* j0 j
   
2.     if (left >= right) {$ G% J& r3 H: b. v% D
   
3.         return;1 z0 s6 L% r1 D\" J\" x# _* I) Y  }
   
4.     }+ y6 l: {. G; J
   
5. 
   \" N) {3 q1 [) ~/ Y* C# y8 l) E7 `
6.     int mid = (left + right) / 2;
   5 C2 J4 ]! S! y8 d1 G% R$ X. i1 S( W
7.     mergeSort(arr, left, mid);0 M0 ~' @) D\" p6 ]- [
   
8.     mergeSort(arr, mid + 1, right);
     a: V$ y; o0 c' W& p
9.     merge(arr, left, mid, right);; D8 i% V( s, H
   
10. }
    ! n* \0 @& Z$ n+ a
11. 5 S7 j+ G0 P0 \\" q' O. Y2 }
    

复制代码

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

对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
  L" z' Q# g' r9 D, f! t: b
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   3 K1 V% S+ t4 O( I& V5 u
2.     int[] temp = new int[right - left + 1];
   6 a! l, I( m' X$ d2 ]
3.     int i = left, j = mid + 1, k = 0;\" g: S8 Z' {6 `( G; c+ E
   
4. \" l' l9 |  i( {0 [) i\" f
   
5.     while (i <= mid && j <= right) {
   , K. B' C8 B) ]! }1 b8 ^
6.         if (arr[i] < arr[j]) {
   \" v$ Y' @/ m5 R
7.             temp[k++] = arr[i++];
   1 ~$ E, V, ]. u  _
8.         } else {
   & }  F) d( B8 P8 V0 B8 q
9.             temp[k++] = arr[j++];
   2 p- L! P% W. p$ w$ D2 X
10.         }
    % J9 K, R; u! S\" o
11.     }; `  Q# U8 w7 K: Y
    
12. # ]% _5 ^* ^2 h! D8 G\" c$ I: o3 o
    
13.     while (i <= mid) {! P+ S, I. X4 f, e) @) G2 Q
    
14.         temp[k++] = arr[i++];
    ) S7 y& d6 [, k5 S( Y
15.     }
    ( Q+ j& T& h% l+ D; Q, V! `0 Y
16. 
    + d! p& |) }* H) e, i
17.     while (j <= right) {
    3 Z  P2 U' A1 b; F2 z* m
18.         temp[k++] = arr[j++];* L. o4 e\" i) |& i5 d3 X$ D* ^
    
19.     }, \3 M: N* J- M$ u
    
20. 
    $ C& X  u& C. w# \
21.     for (int m = 0; m < temp.length; m++) {% P* O$ f8 `6 c) g
    
22.         arr[left + m] = temp[m];: U5 m1 C! e* K) q& f+ Z
    
23.     }
    ; v. ~4 O$ w1 j  u. n# F
24. }$ T% y7 o2 O4 a+ W
    

复制代码

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

6 K' [/ Z# e: [3 W合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
- S" s, Y# ~8 g% I+ x
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
- o6 r8 A" X; l( s


/ _, m! i2 \% T6 S7 [
2 w# H. g# E+ V9 m6 }