数学建模社区-数学中国

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

---

作者: 2744557306    时间: 2023-11-29 10:20
标题: 深入解析排序算法之——归并排序
1 基础介绍
( Z+ z0 u3 Y( r6 Y. h- u. B; J排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

8 r/ ~0 L$ }6 k: Z以下是一些常见的排序算法：

/ r! _2 Q1 |7 m% ^+ _冒泡排序（Bubble Sort）

' W: h% |5 r6 `2 k& x9 c' I插入排序（Insertion Sort）

选择排序（Selection Sort）
9 I  x# O. r# u& u) Y% @
归并排序（Merge Sort）

' c1 T* n% O. F快速排序（Quick Sort）

堆排序（Heap Sort）

一、基本介绍介绍
1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
4 A5 n6 e: ?, ], |% r
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
7 o4 H# h" W9 {' A' N% z1 d! f2 V
2 e7 A. f9 D8 Y8 p& W+ K分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
6 K; Y8 ~2 v# f- T1 o! S  W8 K" r7 T
( H1 Q; ]5 I9 M4 S2 f# Y( h/ t合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
% A$ n3 z8 {: z6 E0 L+ D! h) L
3 B; ?* |% H- F; \8 v合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：

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

比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
# ^" O! g2 S, @" y: B( |' z
, s% ?1 p( P. o, w将另一个数组中剩余的元素放入 C 中。

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

/ S% D% {) i2 _4 u原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。
1 }1 A6 Q% c) V* @
9 n4 ^4 F& d7 N1 U5 Z对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
' X/ Q0 j. A7 i6 K/ m7 S
3 U5 o( O8 L' N接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。

1 J1 @; n: q- R2 K0 K- m将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。
8 q$ n8 u' C7 g* Z
0 z' x3 C3 |% E. O% k  r因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
$ a8 |$ Y- v2 H0 W
. P, E" G2 ?1 a/ o* t; f4 q1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
, z3 c' Q3 O8 S1 B/ Y
/ l$ f/ e1 R$ Y这个复杂度可以通过分治的思想来解释。

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

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

" W/ u1 C4 E2 I& u) v归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
& a% n2 r, z4 n/ p+ |
) Z  K% o8 v. \# r( ]% s这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

0 L0 o6 F  g- o8 S3 M7 a& q1.3使用场景
* D/ |9 e, e# O4 @, B7 R归并排序的应用场景比较广泛，主要适用于以下几种情况：

1 a& X) j% t1 U* a, _5 g对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
$ H" k4 [  Z. I. ~
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

* k  k9 V. C% X; T对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
3 r( q" \) |* ^1 b& w0 g2 u+ P
1 e  n. @( [1 E+ _; S对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
& X* c  K) V2 H- ^8 R
对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
/ F1 o# Q2 z3 X* G; W; E
' z0 x# n, j. R; P7 [总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

: |* ~4 f* v* R. \6 I二、代码实现
& r- [6 {$ \3 M6 X2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   
3.         return arr
   
4. 
   & ^& X& s( C0 L, f& A: S
5.     # 将数组分成两个部分
   ; A# r7 O3 K$ T
6.     mid = len(arr) // 2
   % ]' R2 U: i; `1 o8 t: I0 _( j
7.     left_half = arr[:mid]
   
8.     right_half = arr[mid:]
   
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    , U2 S) C- j0 @8 D/ K8 ~" w4 E
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    7 j8 r! f7 h' u, |0 o$ @) ^
13. 
    
14.     # 合并左右两部分
    0 P% }5 W. R- f
15.     return merge(left_half, right_half)
    5 I) ]/ O5 k3 w/ e2 R; r5 x" `
16. 
    9 K4 M- V+ N/ m$ S
17. def merge(left_half, right_half):
    
18.     i = j = 0
    5 `1 K  o& Z6 M. Q7 ]$ z9 _
19.     merged = []
    : B3 S- t/ {( O9 l+ V2 G; ^
20. 
    - x8 E9 E* \- u- _9 e0 C4 M
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    
22.     while i < len(left_half) and j < len(right_half):
      s- v% S" r5 |* O9 Z
23.         if left_half[i] < right_half[j]:
    
24.             merged.append(left_half[i])
    
25.             i += 1
    
26.         else:
    
27.             merged.append(right_half[j])
    ( p/ d' s7 `0 t9 g
28.             j += 1
    ' r7 O! X6 V* K6 y6 Z2 r
29. 
    
30.     # 将左右两部分中剩余的元素添加到 merged 中
    
31.     merged += left_half[i:]
    6 S% a) `7 E6 i6 E' b
32.     merged += right_half[j:]
    9 c8 A$ q9 q/ [  w; Y, Z
33. 
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   % z7 `; C! t6 V) |/ o
3.         return arr
   
4. 
   
5.     # 将数组分成两个部分
   
6.     mid = len(arr) // 2
   6 \& D+ y8 H& a4 l& K
7.     left_half = arr[:mid]
   / V, N( H4 H6 y8 k% p6 _
8.     right_half = arr[mid:]
   
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    : l4 I8 q) _/ U# l0 i4 K
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    
13. 
    8 |' B& n9 W" q. G# S3 P( K8 \
14.     # 合并左右两部分
    $ e3 w* ]+ b+ z7 W$ U6 U* a
15.     return merge(left_half, right_half)
    0 u, u  n& M2 ^( z
16. ```
    / A% R# b) M0 {
17. 
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    

复制代码

merge() 函数

1. def merge(left_half, right_half):
   & O# h) i% w1 y
2.     i = j = 0
   / b' Y5 |" Z! Q- M" i$ s& V3 K
3.     merged = []
   
4. 
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   1 W" F4 j& ]# m- S  ]$ O7 ]. o* D
6.     while i < len(left_half) and j < len(right_half):
   
7.         if left_half[i] < right_half[j]:
   
8.             merged.append(left_half[i])
   
9.             i += 1
   ) J1 W6 W8 W7 T, w2 R
10.         else:
    
11.             merged.append(right_half[j])
    
12.             j += 1
    
13. 
    6 x8 i- M+ A& N$ @! [6 N
14.     # 将左右两部分中剩余的元素添加到 merged 中
    + P7 p% I1 U5 a! C0 h  ^
15.     merged += left_half[i:]
    3 u, C0 B  ^; ^
16.     merged += right_half[j:]
    
17. 
    + ?6 |, c8 x; r5 L. P9 J" H
18.     return merged
    
19. ```
    
20. 
    % S0 k8 N+ {- C; u: p5 m+ e
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
$ w1 x# A" m) p) K+ d
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
! K4 R! j% q# L7 ~2 u5 a; u& p
将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
8 ~" L4 U5 K& M+ E% O
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
1 f* N" B" D7 U1 w" G+ i
测试
/ i8 [: t) `9 J* A4 ]0 l在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   9 [& }  h1 ?! @3 P) S2 E
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {
   * b" t) n- L- C* F6 B* L- Y
2.     public static void main(String[] args) {
   
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   3 f" X0 `$ T3 h2 m, l
4.         mergeSort(arr, 0, arr.length - 1);
   2 q8 c6 g$ O6 A8 {6 D. e. D" ^7 x
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   6 m3 R# x$ U, y' A% i
6.     }
   3 H, Y5 V; p( b$ v# ?5 X
7. 
   % T% s6 {. L1 L4 K5 x- ?5 x
8.     public static void mergeSort(int[] arr, int left, int right) {
   + ?8 ^* A3 E+ n' I: T! g# c  F. b5 A
9.         if (left >= right) {
   9 n9 v( b5 s. B2 I0 ^
10.             return;
    5 T# O0 A+ F2 @! E8 k* C6 a
11.         }
    : O. L4 R3 N0 h  \) i; ~$ f
12. 
    
13.         int mid = (left + right) / 2;
    
14.         mergeSort(arr, left, mid);
    % P  \9 ~: f6 B# s& V
15.         mergeSort(arr, mid + 1, right);
    
16.         merge(arr, left, mid, right);
      @$ _+ t0 n5 h6 ]" r+ t
17.     }
    
18. 
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    6 s. Z( v4 m+ d6 y* a6 p
20.         int[] temp = new int[right - left + 1];
      w' F( D) J& {& A, G9 l
21.         int i = left, j = mid + 1, k = 0;
    
22. 
    : z& C- @; h0 v0 t$ [$ u
23.         while (i <= mid && j <= right) {
    " H6 B5 @6 Q  S( j$ W
24.             if (arr[i] < arr[j]) {
    
25.                 temp[k++] = arr[i++];
    
26.             } else {
    & ^% b; C7 {8 v6 P" |! _7 C  B
27.                 temp[k++] = arr[j++];
    
28.             }
    ; _, ?% }$ z( x
29.         }
    7 g; e, ]  C' W0 n) B
30. 
    
31.         while (i <= mid) {
    
32.             temp[k++] = arr[i++];
    
33.         }
    + ^& ~* C! P9 B" O( S
34. 
    
35.         while (j <= right) {
    
36.             temp[k++] = arr[j++];
    
37.         }
    
38. 
    
39.         for (int m = 0; m < temp.length; m++) {
    
40.             arr[left + m] = temp[m];
    
41.         }
    * b4 ]* l+ P3 N% w" m
42.     }
    ) k7 O+ U1 u% [
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   : G) i/ L# w4 O* v8 d- m
2.     if (left >= right) {
   / K6 R) k4 Q# u: q! }
3.         return;
   * n* D7 ?) ]% k% \8 K3 }
4.     }
   , X+ r" ]' l  Y
5. 
   : v4 Q/ d: y5 r; c  ?) b$ v
6.     int mid = (left + right) / 2;
   
7.     mergeSort(arr, left, mid);
   - E) ]1 h$ p0 q- C0 b6 ~. G
8.     mergeSort(arr, mid + 1, right);
   4 W$ _$ G( S2 L
9.     merge(arr, left, mid, right);
   
10. }
    
11. 
    + |1 }- X* U# [  ]$ y

复制代码

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

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

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

1. public static void merge(int[] arr, int left, int mid, int right) {
   
2.     int[] temp = new int[right - left + 1];
   1 c1 A5 N- k7 o& e
3.     int i = left, j = mid + 1, k = 0;
   
4. 
   
5.     while (i <= mid && j <= right) {
   
6.         if (arr[i] < arr[j]) {
   , [1 u% X  u/ {1 ]( t
7.             temp[k++] = arr[i++];
   
8.         } else {
   ) k" h* ]4 c; {$ |
9.             temp[k++] = arr[j++];
   9 T) I# h! U/ b
10.         }
    0 r& @! y6 g6 h) ~
11.     }
    $ r# P4 d  Z" |$ P% z0 M* ?2 b
12. 
    
13.     while (i <= mid) {
    * F! T% A3 S: |5 `) y
14.         temp[k++] = arr[i++];
    # B5 w3 A4 c/ [& g2 U2 C* W- b
15.     }
    3 k9 W! l5 R% r6 C3 ]
16. 
    
17.     while (j <= right) {
    0 y4 c. d  e! b4 P& u+ K4 t% O" G
18.         temp[k++] = arr[j++];
    
19.     }
    
20. 
      {! R6 M2 d) w# a
21.     for (int m = 0; m < temp.length; m++) {
    * i4 N7 [# N" C2 m
22.         arr[left + m] = temp[m];
    
23.     }
    
24. }
    # d4 Z, \9 s5 a" Y' Z

复制代码

这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 temp 来存储合并后的结果。
  p7 x7 A& a, g1 {  [' X  z
9 a3 G! F( ~0 D* V+ f" V  z" |* h合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

# C. A3 P% J7 b6 t1 w最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。

需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。
, o& q- X; {6 C* e* s' U

# H8 Z& Y/ L4 x
. J0 V  q! o* d- Z7 c+ m

7 x: n* h2 J' l: `* v2 n
' Y5 j* w8 P8 l, @) ^9 l' H! y
! M9 F) c+ f' q2 U# Z0 B2 \: C' F* Z5 v0 p

---

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

Powered by Discuz! X2.5