数学建模社区-数学中国

标题: 深入解析排序算法之——归并排序 [打印本页]

---

作者: 2744557306    时间: 2023-11-29 10:20
标题: 深入解析排序算法之——归并排序
1 基础介绍
- D% u3 m$ ]8 Y7 p/ O6 }4 V/ i排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。
5 G* Z! Z' O4 V/ ]
以下是一些常见的排序算法：

冒泡排序（Bubble Sort）
6 ?* ]$ `' ]# r, u( q" N8 O% z0 L
插入排序（Insertion Sort）

$ O$ r$ _- f# d1 [: Z  V5 O( T选择排序（Selection Sort）
  f# m3 q$ e/ L9 U, t
2 b) W2 Z% `5 [) u归并排序（Merge Sort）

% T0 H9 P: P4 L" a' m2 }; E; D! m( n快速排序（Quick Sort）
" h5 Q5 l% p. M( [* A6 m- X
堆排序（Heap Sort）

一、基本介绍介绍
2 x6 x/ j4 M4 f' k% i, l; {% F1.1 原理介绍
+ n) i6 N" R  k* ?$ o0 b归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
1 g5 f5 j6 v. ?
( |# i4 F/ G) ]2 V6 g归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
$ S) T( i2 P6 O! B
分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

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

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

定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
# X' H% a8 k9 u7 c7 W% \
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。

  y. F( L$ G: n将另一个数组中剩余的元素放入 C 中。

归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
' w1 n2 T4 D# u. H5 j! W+ L
1 C0 w1 H# Q" B, r2 N- a% a原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
7 a2 x# Q9 q; ^' @6 H/ c
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
1 j9 b+ C9 |! D( A1 W
: c1 G% m' \2 U6 f/ c首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
" t- g/ E5 E* m: I7 u7 R$ O
对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

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

' w4 S6 ~4 u, O! [) k. c因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
2 J+ x3 c7 c( f& v8 U+ L; Q7 h
1.2 复杂度
+ _9 p8 ]! z+ c7 `0 E归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

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

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

6 J* j# C. N- `) `0 |# }! K每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

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

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

0 C5 A% i1 X$ g" P9 W* x1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
1 y6 z* ^/ [0 }
6 Q" y( W1 Q5 }对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。

; |! t  t) d% _6 I# N6 Z+ `对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
# m- k6 o( C9 ~' T( S+ u* O
* }3 B( W4 P. K- l7 V7 x- B对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

1 c* j% Q! T) r5 ?! _对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

. i* H$ B+ ?4 s% y( q, p对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

! q2 B. A/ i7 T) o1 m. _/ A1 l; _7 x总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
  Y" |) `9 z8 z1 [! C; r
二、代码实现
; Y3 ~/ z, h# x: s2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   
3.         return arr
   
4. 
   
5.     # 将数组分成两个部分
   : n6 c$ R6 X1 O. h6 l) z; o$ r) A/ K
6.     mid = len(arr) // 2
   
7.     left_half = arr[:mid]
     i, k. T9 F: i. a5 n, V# S% s
8.     right_half = arr[mid:]
   ) f5 [6 Z* z/ }
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    + O+ Q& A0 b8 z5 I  z
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    7 T; p! S; o6 O' X9 `
13. 
    
14.     # 合并左右两部分
    
15.     return merge(left_half, right_half)
    
16. 
    & b. v& \/ w& p: }. ?( k5 J
17. def merge(left_half, right_half):
    . S' A' w! F: c, q% b/ N) E
18.     i = j = 0
    $ k/ \! l& }+ q; r. z3 P& R6 i
19.     merged = []
    
20. 
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    & P+ Z/ h9 D1 W( Z) |" V2 W
22.     while i < len(left_half) and j < len(right_half):
    
23.         if left_half[i] < right_half[j]:
    / O. [" [1 H4 T3 s1 r6 `  A4 X
24.             merged.append(left_half[i])
    ' a  }# o# C" F- d+ ~9 C
25.             i += 1
    8 n0 z3 A. T  ]- d6 h
26.         else:
    
27.             merged.append(right_half[j])
    
28.             j += 1
    4 I: R9 Z; R8 m
29. 
    ! E% Z1 {" ?3 m5 h3 f# |1 F
30.     # 将左右两部分中剩余的元素添加到 merged 中
    + t, Y. N- X: o, u8 [
31.     merged += left_half[i:]
    ' k& @! s( U1 d) q
32.     merged += right_half[j:]
    
33. 
    ; N- `  A- V; m' d* G
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   2 G. s0 C" `, Y' M
2.     if len(arr) <= 1:
   
3.         return arr
   # Y: m$ l( l! ^7 q
4. 
   % i2 u" T6 S( A' \7 K4 U0 R; d
5.     # 将数组分成两个部分
   7 [( w4 T, e; i6 g  B- l# H
6.     mid = len(arr) // 2
   
7.     left_half = arr[:mid]
   ' E0 R# {+ T& N$ G1 q
8.     right_half = arr[mid:]
   & d$ [/ q- I$ p6 L
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    
13. 
    . L+ f$ m( I2 S
14.     # 合并左右两部分
    
15.     return merge(left_half, right_half)
    3 [8 k+ G: w5 x+ n
16. ```
    # |  u) g7 {7 X- ^' D( D# S2 S
17. 
    ! ]. k7 S3 T# W5 M% f
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    9 ~7 C& V2 Q; L, [# o- d0 t

复制代码

merge() 函数

1. def merge(left_half, right_half):
   
2.     i = j = 0
   
3.     merged = []
   
4. 
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   5 M7 a9 y9 `& G' t6 v$ n
6.     while i < len(left_half) and j < len(right_half):
   
7.         if left_half[i] < right_half[j]:
   1 h+ s% T# p5 ]9 @2 C/ v) y9 P! A
8.             merged.append(left_half[i])
   ! J8 f7 h: L$ z& K( ^* P& q0 D
9.             i += 1
   
10.         else:
    8 w( X3 T0 n( S3 K/ F
11.             merged.append(right_half[j])
    # ?* L. H' O7 q4 ]
12.             j += 1
    
13. 
    ! D6 m3 O, x5 l; r7 O3 _
14.     # 将左右两部分中剩余的元素添加到 merged 中
    % ?' Z, c  h, ^/ Y5 d, @
15.     merged += left_half[i:]
    
16.     merged += right_half[j:]
      M* E* _! j! @* H1 F
17. 
    
18.     return merged
    
19. ```
    6 y- a7 v8 u" H0 P
20. 
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
* y) Z0 W+ ^# E- {' r. Q
0 Z, ~, a! Y8 J7 J* J" [2 L. `判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
+ Q3 J9 a) L. K: S$ t
6 G/ p% \# Z: {0 E8 K2 b将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

. h" L5 H4 U# ^) `; C0 W- }  p对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
. Q: T/ z3 A' g1 u: O
测试
) a. q, b4 X; \, |在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   , J+ }6 D; ?; G5 x& E
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {
   ; M1 ~+ _0 k; _) r9 j! t( D: {
2.     public static void main(String[] args) {
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   
4.         mergeSort(arr, 0, arr.length - 1);
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   + e/ [. M; }" b! R; ~% u
6.     }
   
7. 
   + j4 `, f. _0 v$ U# \2 V* o
8.     public static void mergeSort(int[] arr, int left, int right) {
   5 Y& h2 ^& k% v7 i0 S
9.         if (left >= right) {
   * L5 m( j  W2 }1 o! \' `/ _% A
10.             return;
    : K: P+ V- n7 m& K: S
11.         }
    : ~2 {  R% G- e" t, f) x) ?
12. 
      `! P. }+ r% R& }  Y/ x
13.         int mid = (left + right) / 2;
    ( V  Y* S- o# i$ n
14.         mergeSort(arr, left, mid);
    ( }) z& ]+ O3 J) q& m
15.         mergeSort(arr, mid + 1, right);
    
16.         merge(arr, left, mid, right);
    
17.     }
    + p8 C0 t, [8 I& t9 F
18. 
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    
20.         int[] temp = new int[right - left + 1];
    * _3 q5 Z( L  v" Z, G, c3 Q4 s
21.         int i = left, j = mid + 1, k = 0;
    9 m" h  w! ~- a# U  C6 k
22. 
    
23.         while (i <= mid && j <= right) {
    
24.             if (arr[i] < arr[j]) {
    / l3 `, F# D5 p. Z
25.                 temp[k++] = arr[i++];
      Q$ r$ ?- [& A6 U
26.             } else {
    
27.                 temp[k++] = arr[j++];
    ) t. ^9 i4 I/ Y; N% }9 ~
28.             }
    
29.         }
    4 D+ W. b+ F# S$ p# l
30. 
    
31.         while (i <= mid) {
    
32.             temp[k++] = arr[i++];
    3 Z) V- c& ]8 o
33.         }
    : l3 _' W& f) X; Y. n0 T5 G  m8 H2 B4 t
34. 
    & |, E1 @  z- Q+ K
35.         while (j <= right) {
    
36.             temp[k++] = arr[j++];
    
37.         }
    
38. 
    ' E% [3 ~' w" z5 [; ?$ G
39.         for (int m = 0; m < temp.length; m++) {
    
40.             arr[left + m] = temp[m];
    $ M5 u4 N+ M+ k6 s9 L* D
41.         }
    
42.     }
      f6 n. g3 P' [! `2 M
43. }

复制代码

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

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

5 }! b6 p1 ]8 v( G7 ]mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   
2.     if (left >= right) {
   / S) q% [- q- T# m* Q
3.         return;
   
4.     }
   7 ^1 U* D  {+ i/ O
5. 
   ) J: s, [. d" @/ M9 U0 A7 E+ C
6.     int mid = (left + right) / 2;
   
7.     mergeSort(arr, left, mid);
   , @1 M* i& y( c0 O4 I8 U
8.     mergeSort(arr, mid + 1, right);
   
9.     merge(arr, left, mid, right);
   2 A7 ?0 d* ]4 c% Z) k, S
10. }
    ! ~* L  V' C' P3 Z
11. 
    

复制代码

这个函数使用递归的方式对数组进行排序。
! C% q6 q; h( b) e5 Z  j" ]
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
3 [8 O7 c+ t6 Y
9 ^' w, a& ?( {- C5 p最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   ! T# G! Y$ S1 e9 w  x0 f
2.     int[] temp = new int[right - left + 1];
   
3.     int i = left, j = mid + 1, k = 0;
   
4. 
   3 ?! W+ ~, [7 U
5.     while (i <= mid && j <= right) {
   9 Q7 y$ d. I9 {( _  N4 z2 p" C3 r9 e
6.         if (arr[i] < arr[j]) {
   
7.             temp[k++] = arr[i++];
   
8.         } else {
   . s; b$ L" p+ D  Z
9.             temp[k++] = arr[j++];
   
10.         }
    
11.     }
    ! d' ~' d* d: i# @) M" [1 r
12. 
    
13.     while (i <= mid) {
    * r9 L6 B5 c4 t2 @
14.         temp[k++] = arr[i++];
    ( x% F& P: s2 V# X' h) D
15.     }
    
16. 
    
17.     while (j <= right) {
    
18.         temp[k++] = arr[j++];
    5 c* `5 K2 k& e. s' e( O  J
19.     }
    7 P5 E4 k. y- P! Z+ y
20. 
    ' B+ r3 t/ h% _# y9 X5 }
21.     for (int m = 0; m < temp.length; m++) {
    
22.         arr[left + m] = temp[m];
    
23.     }
    
24. }
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
1 n4 m& K5 y/ Q# R9 D& W. w
6 t: M7 P2 I; M, h9 f: W合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
$ H+ \. R9 z2 G7 n4 {$ D4 H
! t' m$ F  j" f5 r0 {  n8 K需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
9 L- V7 ]% s  v% D; @: i
1 Q: Z6 }) T& z1 w7 y这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
$ Q1 M3 b( U" X8 \! z* Z3 A# X

0 |# F) r$ @* n5 f0 o

+ K* i0 `3 ^1 D
% G4 Z/ A4 W' q8 r9 b: |) z
) q* p% j0 ]! Q) M& I
  i" W- H( l& ]2 ^

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5