数学建模社区-数学中国

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

---

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

: O2 j: d* o) H5 H: l/ b1 p# Q以下是一些常见的排序算法：
. K. u; c* {5 o, e/ l" [
5 X3 U9 j. r5 c+ ~6 x0 o: O冒泡排序（Bubble Sort）
& F7 ~) V  O) u  y$ ~: u- I
插入排序（Insertion Sort）
7 e0 E5 p$ R5 o# h  m5 \
选择排序（Selection Sort）
$ q2 a7 s2 ?2 @. I  e; h7 w
2 b5 ^5 l( B! w归并排序（Merge Sort）
4 l/ p( L1 p0 ?( I) P# m$ {+ V
快速排序（Quick Sort）
4 W. q" U3 [: u
. s2 l$ D9 w# Q0 i9 B& f堆排序（Heap Sort）

一、基本介绍介绍
; O" j/ y7 Z& a9 O# h/ H  w: y  @1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
4 l5 n7 v7 C1 b% i
, M3 |/ F1 p( j# C分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
9 r" p& R6 b( j0 a% H
+ b+ B" A; a5 L, M合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
( k5 M' r2 X7 [; N
  T4 b% l" @7 x0 E! A& j合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
% x1 h: }% e, s, P: E( i1 W& Z
定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
( A; C7 n1 r( ?3 q2 Y
# M; q  l2 B2 ?& m$ k比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。

重复步骤 2，直到其中一个数组的元素全部放入 C 中。
) J0 D/ ~" A3 [1 t& n$ u" |
$ a  d' \8 |" u. X) f将另一个数组中剩余的元素放入 C 中。
$ l, Q0 H( t: x3 l# b0 R$ ]
归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。

( }, W3 D: }/ I原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

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

8 b: v' U; u9 ^# ?9 b首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
) ]' r/ I/ D8 R2 y
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
- o" G/ J0 E  I" Q- p* ~- A8 ]) ]
将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

/ u+ Q! f" p; M! C6 t因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。

1.2 复杂度
0 J: ^3 @3 q4 q1 A/ H) D! T归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
1 G% O# |' e5 Z2 p$ L( u: w  V  n
) J( C6 J- F& q/ ~9 n这个复杂度可以通过分治的思想来解释。
( J5 J1 T( e9 _' Z' H
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
7 U: _% j$ j- Q5 K
9 v/ @% V8 h* h0 ]# p每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
" J- g. c9 ]1 X- T. m% W- K  N
归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。
! |9 z, F" ^, h1 t" g4 ?. T% A
这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。

' z- G1 U* K4 `& {1.3使用场景
5 O% h0 p: h7 k; q, q归并排序的应用场景比较广泛，主要适用于以下几种情况：

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

对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

, |: g, \8 w0 W- g! l对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
. k: g8 o$ }+ |
4 O% V1 l" a" S! T8 v: I9 o对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
( t/ A% y5 j; k5 w, i
总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
2.1 Python 实现
4 ]# l  b6 s( S. ]5 E$ @$ O  u以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   
3.         return arr
     o  E4 w  {; r' v- x2 S
4. 
   
5.     # 将数组分成两个部分
   / F' ]  h- O& V7 ^$ n" ^% F: y* C$ l
6.     mid = len(arr) // 2
   
7.     left_half = arr[:mid]
   
8.     right_half = arr[mid:]
   
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    
13. 
    3 z( u, I& V2 t: p
14.     # 合并左右两部分
    ' E* b; K. v# V! I
15.     return merge(left_half, right_half)
    
16. 
    
17. def merge(left_half, right_half):
    9 f, d) M( z, \- h' x+ U3 |- Y
18.     i = j = 0
    ) O: Y1 ]8 a5 k# D/ ~$ o
19.     merged = []
    # c4 B" F4 D) O7 V" f
20. 
    
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    6 ~- P( I7 C' G$ N* W+ A
22.     while i < len(left_half) and j < len(right_half):
    2 G  [3 ^* B  s0 W) q" ?1 h4 o
23.         if left_half[i] < right_half[j]:
    
24.             merged.append(left_half[i])
    0 x3 K" a, D+ q* Q: Q: L9 N2 ^" N. u
25.             i += 1
    % O! C- q. ^$ h& k$ n
26.         else:
    ( I+ t, d: P$ t  q0 b* @% C3 p
27.             merged.append(right_half[j])
    
28.             j += 1
    
29. 
    ( j! @% Y/ l4 O6 t* j' j* h
30.     # 将左右两部分中剩余的元素添加到 merged 中
    
31.     merged += left_half[i:]
    - Q4 ~) Q: N$ z- Q. F
32.     merged += right_half[j:]
    " ]) V3 c( k$ j; G
33. 
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   4 o' @9 G( s4 y9 j  Q9 q
3.         return arr
   
4. 
   
5.     # 将数组分成两个部分
   * W# Q$ [1 c: O! }. G% i7 }, _
6.     mid = len(arr) // 2
   $ C8 g  b* O- a! d' P: K$ c
7.     left_half = arr[:mid]
   
8.     right_half = arr[mid:]
   
9. 
   
10.     # 对左右两部分分别递归调用归并排序
    * W7 {3 y0 V3 X) [/ c
11.     left_half = merge_sort(left_half)
    1 t2 C8 ^, Q5 x: {; M$ k) i
12.     right_half = merge_sort(right_half)
    & v$ T7 A- k% X; f9 d& r8 T% R  P
13. 
    
14.     # 合并左右两部分
    . [# k- J. n+ K% h5 r7 f7 P4 ?
15.     return merge(left_half, right_half)
    
16. ```
      v4 o: x! r' f  _, I
17. 
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    & F- U1 w0 P. {7 C2 F1 `- n

复制代码

merge() 函数

1. def merge(left_half, right_half):
   
2.     i = j = 0
   - v. }% l# i1 m" b# |1 k
3.     merged = []
   % v$ B2 E/ d0 _6 u) M, O& T
4. 
   
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   6 D% B7 B3 y, D" @3 H0 r
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])
   " D: W+ F) y! ^7 X9 o# Y
9.             i += 1
   
10.         else:
    
11.             merged.append(right_half[j])
    " n  \* }" y$ f3 F* V
12.             j += 1
    
13. 
    
14.     # 将左右两部分中剩余的元素添加到 merged 中
    ( C% d) T" L  [( c
15.     merged += left_half[i:]
    
16.     merged += right_half[j:]
    3 {' a$ f8 n/ x
17. 
    4 {; m+ I  A9 m
18.     return merged
    
19. ```
    1 O( }( I: Q2 a/ c) U$ n4 {: H
20. 
    1 _# U% Z% @9 \# i; E
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。
  W8 |  C' F9 _$ W. E7 q' y
& k, H' a; n6 h  s将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

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

合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

这个例子中，将一个无序的数组作为输入，调用 merge_sort() 函数进行排序，并输出排好序的结果。
" ]# {- p1 C, p
总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
; @4 |1 L1 h& K* s! e$ h+ G( i& I$ }2.2Java实现

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

1. public class MergeSort {
   ; K, v7 x7 q% M( n" Q
2.     public static void main(String[] args) {
   5 g# {8 ]/ a2 H, b  R. H: L4 r
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   
4.         mergeSort(arr, 0, arr.length - 1);
   & j0 y- f: L2 k  ]$ j: ]
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) {
   ' d5 l' h4 d" o6 p! p
9.         if (left >= right) {
   
10.             return;
    / x# E; F' \# p3 h: h2 S
11.         }
    
12. 
    / b/ ]+ M1 T' X5 K: b
13.         int mid = (left + right) / 2;
    $ p3 R+ V4 f" C
14.         mergeSort(arr, left, mid);
    
15.         mergeSort(arr, mid + 1, right);
    
16.         merge(arr, left, mid, right);
    * C- b2 @) g1 M/ n# z/ J9 v2 g
17.     }
    * ^1 X. A2 ?- S7 P1 L4 Y' w
18. 
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    
20.         int[] temp = new int[right - left + 1];
    
21.         int i = left, j = mid + 1, k = 0;
    
22. 
    
23.         while (i <= mid && j <= right) {
    
24.             if (arr[i] < arr[j]) {
    / l$ g7 b8 ?' \; c7 S! H. Y0 [5 P
25.                 temp[k++] = arr[i++];
    
26.             } else {
    
27.                 temp[k++] = arr[j++];
    4 R) P) o+ c% g& J) `9 m; s6 v
28.             }
    
29.         }
    
30. 
    ( l1 X% O  F' l6 ~
31.         while (i <= mid) {
    
32.             temp[k++] = arr[i++];
    
33.         }
    ! P8 J' h2 }' H% U
34. 
    $ \$ w1 W1 ?; R* Y8 i/ {
35.         while (j <= right) {
    $ P% P) d+ T* \4 G1 F
36.             temp[k++] = arr[j++];
    
37.         }
    ) G" d1 Q$ e8 e) ~7 C4 }
38. 
    
39.         for (int m = 0; m < temp.length; m++) {
    
40.             arr[left + m] = temp[m];
    
41.         }
    / p" B6 @" e1 z
42.     }
    ( G7 ?! Q$ t2 y8 C
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   
2.     if (left >= right) {
   & g, `& `' }% n) C$ o2 A- `' R5 h8 _
3.         return;
   
4.     }
   
5. 
   0 Z* j6 P  [! c: ^4 P6 {  h
6.     int mid = (left + right) / 2;
   
7.     mergeSort(arr, left, mid);
   $ K  i8 y' j5 s; W7 C/ H! w
8.     mergeSort(arr, mid + 1, right);
   
9.     merge(arr, left, mid, right);
   
10. }
    
11. 
    $ Y) a4 p7 Q5 r/ V- j$ ^

复制代码

这个函数使用递归的方式对数组进行排序。
6 w8 K7 S* |! |$ m% s: U
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
- Y6 D* [: H8 E# u' w" f! K9 t  V
最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   
2.     int[] temp = new int[right - left + 1];
   
3.     int i = left, j = mid + 1, k = 0;
   
4. 
   1 }. G. b% b( F# a* H& W5 Z
5.     while (i <= mid && j <= right) {
   
6.         if (arr[i] < arr[j]) {
   
7.             temp[k++] = arr[i++];
   
8.         } else {
   # P' q0 }- w9 Q! [# T7 V; {- @' e
9.             temp[k++] = arr[j++];
   
10.         }
    
11.     }
    
12. 
    7 ^. y1 K% V" G# ?; h
13.     while (i <= mid) {
    
14.         temp[k++] = arr[i++];
    
15.     }
    
16. 
    2 m* x! O+ E8 r5 q
17.     while (j <= right) {
    
18.         temp[k++] = arr[j++];
    ) g, K$ h! I$ T$ W# F0 j
19.     }
    / e; y* u  Y4 b0 H9 z8 D7 g; @; ?
20. 
    . d1 n' ]/ j  E0 }( e: i1 t
21.     for (int m = 0; m < temp.length; m++) {
    
22.         arr[left + m] = temp[m];
    # d$ }6 E  Q0 g+ X0 d4 n, X  O* a5 [
23.     }
    
24. }
    

复制代码

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

/ h+ \1 m/ ]  M" J. y) }1 R合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

7 L8 e  v$ J& E% ~6 a  a6 ^' ?最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
' @: O+ G- W; y8 L+ i* s2 P2 V
/ {) @* K; I: Z5 v需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
1 b' o, E; E" t7 M6 t1 S- i- ~; m
4 a( J+ p& y2 s: N- i: Y* g这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

4 v5 ]- N. I4 ?" U9 j" D) L  v


( ]& j, I6 F: x1 T1 j
& @7 o: l6 o4 [& k( E

9 p8 `/ Y6 u1 b. p* h: u3 r

---

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

Powered by Discuz! X2.5