数学建模社区-数学中国

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

---

作者: 2744557306    时间: 2023-11-29 10:20
标题: 深入解析排序算法之——归并排序
1 基础介绍
: Z* C+ V) W2 E& B) \& j2 t排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

以下是一些常见的排序算法：
, f$ m% l/ K+ o, W
冒泡排序（Bubble Sort）

插入排序（Insertion Sort）
* ~6 q1 @# \. Z% @  r! |
选择排序（Selection Sort）

归并排序（Merge Sort）

快速排序（Quick Sort）
/ m# d9 w" i8 |8 Z: Z: c" R
堆排序（Heap Sort）
, z/ d3 S0 ]. A, @$ R  A0 m
一、基本介绍介绍
1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
/ J: ]3 z9 T4 \$ x
) s3 }% a" [3 l归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

/ |  G; K. R6 L3 n  y# P- L分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

" V8 W$ M) c: i2 A$ o6 j' u* [合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
" z/ d# f; l4 h' l
3 s/ X* p% `! N$ v/ ~: x合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
6 P, r: N# T  }. u( ~2 N0 ^
  U3 q: A: v, R# l( v# X定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。

比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
1 O, I' h2 w9 ^/ k+ f; L* @% x/ d
! P  J7 M% I9 }* [. i" `重复步骤 2，直到其中一个数组的元素全部放入 C 中。

将另一个数组中剩余的元素放入 C 中。
' E6 h2 B; Q  M- [) S% `/ P  G
  _4 H1 _, `1 r' k) e# A- b归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
0 I# ]* W8 P& d5 t
原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

3 Q$ Z5 X) W0 Y( V" \" i+ x假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
7 d2 P- d" y( E# {6 e- p
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
. s  Q5 `- w# |) C: I$ S" i
( E8 {  L- \: D/ ?( v对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
2 g+ A0 r1 ?+ I8 K
3 B  b9 B+ Q7 T' I  P: U: [& v5 ?对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
& o: H9 f5 ?$ R1 u; e
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
) f2 F* o9 u# h. v5 d. P
, `2 n! y$ d; D' t  P2 U将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
, I5 I) R# \$ {9 Y- K$ a( c
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
9 F6 |8 w/ |( J& `3 F( @. Q
  P. U+ S& T1 V+ p3 j- g# c) N1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

- p# [1 k! E/ ?$ t* w1 O5 B这个复杂度可以通过分治的思想来解释。
; j  r9 |; k0 `' z. X' l- r4 n
( D* T& v; Z# b% h  \7 h' z  Q2 w首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
: W9 P4 N; \# L% l: Y9 Y( ~
每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
! D" N5 U& L+ r3 J  F, _  `
这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

2 ?4 U/ M3 A8 v1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

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

- d5 z, r: m$ |7 p* p对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
" G) _9 O3 s! X2 e
6 L" {0 G4 N+ h( V对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
# I! b# X1 {% j2 \4 C
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

  R3 Y/ O7 U* ^4 \4 C对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。

3 E1 h7 s. E% P5 \' ]( h$ x. J总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
2.1 Python 实现
! t0 d) k4 s& {7 c  W; D以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   
3.         return arr
   , _# a' m6 J$ W$ M9 i# |1 A
4. 
   
5.     # 将数组分成两个部分
   6 z+ ^7 M1 l! ^3 S+ E( V- m, ]( p
6.     mid = len(arr) // 2
   . N  K9 `  ?8 |; {, @$ B
7.     left_half = arr[:mid]
   
8.     right_half = arr[mid:]
   5 n# p, I0 P& O6 @$ f
9. 
   0 A/ v6 J3 d, A; k
10.     # 对左右两部分分别递归调用归并排序
    ( s+ z# w% p6 `* G: D) R7 P) K6 S
11.     left_half = merge_sort(left_half)
    8 g! e/ _) m$ f8 B7 N
12.     right_half = merge_sort(right_half)
    
13. 
    
14.     # 合并左右两部分
    * O" r) s3 i5 o* t. T# G" H& O9 }
15.     return merge(left_half, right_half)
    
16. 
    
17. def merge(left_half, right_half):
    " U. g& L2 \0 x6 j7 }" J* c6 `+ B
18.     i = j = 0
    9 q1 G& i5 }7 V
19.     merged = []
    
20. 
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    
22.     while i < len(left_half) and j < len(right_half):
    
23.         if left_half[i] < right_half[j]:
    $ z7 [7 W/ _: _3 [( V: Q' v
24.             merged.append(left_half[i])
    9 L- }/ S5 w& @) o" o" l
25.             i += 1
    
26.         else:
    
27.             merged.append(right_half[j])
    
28.             j += 1
    - W" e. g- x+ x0 W" z& H
29. 
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    5 {+ ~, [8 H' Y/ X
31.     merged += left_half[i:]
    : Q6 h1 j5 s! e' X
32.     merged += right_half[j:]
      u/ s/ Y2 ?& q
33. 
    9 S5 N, @2 y% n1 \8 w
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   " w; }6 [" V) G
2.     if len(arr) <= 1:
   
3.         return arr
   % `6 X4 v$ g. Q/ [
4. 
   
5.     # 将数组分成两个部分
   ) Q( h8 Y: |! l& @& Y3 l1 ~- x3 `2 u
6.     mid = len(arr) // 2
   
7.     left_half = arr[:mid]
   0 C, m( Z7 M5 C* E4 P; R- ?: F
8.     right_half = arr[mid:]
   
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    
11.     left_half = merge_sort(left_half)
    . p( Q. v. d' t& M. G: h; L
12.     right_half = merge_sort(right_half)
    ! J5 }- `4 T5 U3 I3 t1 {2 @7 h
13. 
    & M9 Q2 t* {9 _* y% }9 S& X, p7 K) j
14.     # 合并左右两部分
      L8 _0 \! _  }. @# y9 c
15.     return merge(left_half, right_half)
    1 Q* }! z/ ^' F* K
16. ```
    ) }9 Z6 O, R1 s; B
17. 
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    % b1 f5 B5 h5 X0 K

复制代码

merge() 函数

1. def merge(left_half, right_half):
   # ^* R8 N9 U; P' Z
2.     i = j = 0
   
3.     merged = []
   1 h8 ]9 L" u' }! k
4. 
   0 O& Q- Q) U- a( [# W
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   
6.     while i < len(left_half) and j < len(right_half):
   8 R9 W) `) F* b8 I: y% ?0 i
7.         if left_half[i] < right_half[j]:
   
8.             merged.append(left_half[i])
   . E7 e9 L8 y  }7 _! u. ]# L! z& E
9.             i += 1
   
10.         else:
    " D* Z( q6 \. D+ e
11.             merged.append(right_half[j])
    ' j1 N, p4 C  k  e  K
12.             j += 1
    3 U, _& q# p' [& |2 j% ?
13. 
    ! t; H1 a& R  P' R/ h4 Q! A
14.     # 将左右两部分中剩余的元素添加到 merged 中
    * y8 _. l+ D8 X
15.     merged += left_half[i:]
    * j! s7 |; \: u: H6 h3 @
16.     merged += right_half[j:]
    
17. 
    + A$ T8 H/ k! T' Y  M5 j6 w$ N/ z  w
18.     return merged
    3 I: L/ g* }3 T$ k2 [" H5 P! K' R
19. ```
    5 }" j# U- E) \, G; n" k, H# f
20. 
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

) G5 T4 D6 G& e6 x: r; i, s+ b) I判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

' q+ |" m3 d" G9 |4 Q) l# ?将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

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

* A+ S3 v$ c8 n  v3 g. x* B合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

5 l2 t( z" m) ^. K# |, T  n3 Z- G/ j  T测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   " R3 q) b$ c- r5 ^; a/ [
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {
   
2.     public static void main(String[] args) {
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   % X% J- A2 x# z! J9 Y5 a
4.         mergeSort(arr, 0, arr.length - 1);
   " h* g- x8 Y  }" N4 f: ~, h8 w
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   
6.     }
   
7. 
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   ' b2 T! @/ s" F( i8 A' }
9.         if (left >= right) {
   7 X7 _5 a. j3 _8 B7 S, R% @( B
10.             return;
    
11.         }
    
12. 
    , W) p  r# }( D
13.         int mid = (left + right) / 2;
      m" ]7 s7 ]- K- @% f
14.         mergeSort(arr, left, mid);
    ! a! h! g) T$ `1 r' s# C4 D
15.         mergeSort(arr, mid + 1, right);
    
16.         merge(arr, left, mid, right);
    
17.     }
    
18. 
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    : A" ?8 v9 g# p
20.         int[] temp = new int[right - left + 1];
    ( X- J3 W2 i, h0 G+ C4 t2 ~5 q8 P
21.         int i = left, j = mid + 1, k = 0;
    
22. 
    
23.         while (i <= mid && j <= right) {
    1 v* ^9 v5 |7 [. a5 {
24.             if (arr[i] < arr[j]) {
    % U+ |7 z/ v: n0 i
25.                 temp[k++] = arr[i++];
    
26.             } else {
    $ S  }. ^0 n$ _
27.                 temp[k++] = arr[j++];
    ( c' t$ [! X4 F4 ~6 T6 v
28.             }
    # y3 C7 o, R* v+ |+ ?( f8 }5 X, i
29.         }
    
30. 
    3 [7 a2 Z7 @* n' M
31.         while (i <= mid) {
    
32.             temp[k++] = arr[i++];
    5 y; r+ X6 D. l- V
33.         }
    
34. 
    
35.         while (j <= right) {
    
36.             temp[k++] = arr[j++];
    
37.         }
    + @/ B' ]) A7 a9 Y! s
38. 
    
39.         for (int m = 0; m < temp.length; m++) {
    
40.             arr[left + m] = temp[m];
    2 n+ F: J9 }& A+ `; d% a
41.         }
    
42.     }
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   % i* q) \% m9 |6 ~3 x5 z
2.     if (left >= right) {
   . ]. _. \7 L+ e
3.         return;
   
4.     }
   ) ^2 V! H+ ^0 d8 w* p8 ?) @6 d& A$ f
5. 
   
6.     int mid = (left + right) / 2;
   
7.     mergeSort(arr, left, mid);
   
8.     mergeSort(arr, mid + 1, right);
   
9.     merge(arr, left, mid, right);
   
10. }
    & L6 ~& D) v+ p( |% \6 M
11. 
    2 `0 M2 d! d, Z( i% T4 J4 ^% S7 c# E

复制代码

这个函数使用递归的方式对数组进行排序。
# {3 j. e" m* m! Y  u/ g
& f) z0 b3 m2 {3 e7 y, V" Z对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
" P# a/ N, G9 E* G; n
, S3 N5 s! G, L- C; @( x最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
, `0 d) }( C) k' q( @merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   - a7 I! ^" r* k4 I
2.     int[] temp = new int[right - left + 1];
   
3.     int i = left, j = mid + 1, k = 0;
   * x0 Q2 W9 \  x7 r( J1 x% c
4. 
   
5.     while (i <= mid && j <= right) {
   $ z' c0 J$ q& A
6.         if (arr[i] < arr[j]) {
   
7.             temp[k++] = arr[i++];
   5 `, A3 k1 Y0 C4 v
8.         } else {
   
9.             temp[k++] = arr[j++];
   9 n5 X+ a( w. y- q& q: |% T
10.         }
    
11.     }
    
12. 
    ( `6 {+ c' W9 F4 V
13.     while (i <= mid) {
    4 ~; g' P5 j" f" ?0 M
14.         temp[k++] = arr[i++];
    
15.     }
    
16. 
    + h; Y& X6 u; |/ r
17.     while (j <= right) {
    
18.         temp[k++] = arr[j++];
      f) m0 X' I* A4 [1 N2 p* h! {1 t8 O
19.     }
    ' I( {5 O4 Z( i+ R$ l/ W% U
20. 
    
21.     for (int m = 0; m < temp.length; m++) {
    + V. p1 S9 o. H4 U! E
22.         arr[left + m] = temp[m];
    
23.     }
    
24. }
    

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
3 s1 R! a/ e! i5 n; u% a
合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。
0 B" |! m5 _* H
最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
- V7 p, B1 ~9 g
) s6 _& z& X$ n) |1 p# R6 j, K需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
, N) G. ^! \2 G
这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。


( ^6 I% l9 r8 A4 C: N6 h# D

' [1 h- G* _0 @! S, D" p: H
1 C$ D) `) ?# R0 x  E

3 |! l% y1 s7 L/ G" t# m  O

---

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

Powered by Discuz! X2.5