数学建模社区-数学中国

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

---

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

以下是一些常见的排序算法：

冒泡排序（Bubble Sort）

插入排序（Insertion Sort）

7 f1 K7 U% D" q' i6 y4 h选择排序（Selection Sort）

3 v' ^; p9 ]+ r7 J% V归并排序（Merge Sort）

, n- T, k, E' |2 S/ o* C" J1 q. M快速排序（Quick Sort）
5 k* @- o  A' w/ K
堆排序（Heap Sort）

一、基本介绍介绍
1 m' [& L- H" B5 T/ g& R1.1 原理介绍
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
' }" z+ f4 p' u& I( J: F1 `* s
归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：
9 T/ R& T! ~$ Z1 o* ]3 n
; E# }; N$ s0 k2 T分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。

合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。
: L; o" `2 C3 y' j6 g
9 g& ^  ^6 s' F. T合并的过程中，需要用到一个辅助数组来暂存合并后的有序数组。具体来说，假设待合并的两个有序数组分别为 A 和 B，它们的长度分别为 n 和 m，合并后的有序数组为 C，那么合并的过程可以按如下步骤进行：
* O3 ?. u6 q2 \5 I8 E
5 @) l8 g5 z: @+ w; `定义三个指针 i、j 和 k，分别指向数组 A、B 和 C 的起始位置。
3 O2 Z3 ]2 F2 f7 I9 g  X) s
比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
- q5 J/ K8 f$ w. u, B8 M
重复步骤 2，直到其中一个数组的元素全部放入 C 中。

& W; ^- }- Q5 X2 S* @0 o7 ~$ z将另一个数组中剩余的元素放入 C 中。
( p. ?! O) f" m* r# d
; @$ d. y; G" l$ t2 I7 h归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
" m2 b2 h* N0 g! a  M
" L. x& C; P* U% ~0 n8 V2 H原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：
. N. R' T  R" f  a& t1 ?4 U7 F
8 D( K% Y! U3 R' D, I6 p0 s假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
& o' u# o, o! ~' F
( K% q$ {8 Z, Q; V% X$ b首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

3 M8 Y7 D! \5 U  S5 D$ T, |8 M/ B* @+ a对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。

& G6 n4 s2 `8 m+ ?对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。
& y/ Q! C  F5 M3 i, u
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [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]。
* o8 k/ K. Y1 W: Q/ x/ u# k
因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
5 q  G0 g, T0 {
1.2 复杂度
) E" S8 S/ [0 T5 v0 r  l. V归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。
4 U  P" Q& R; y/ Q) E
- c- M% e( j6 A' Y6 _* H这个复杂度可以通过分治的思想来解释。
. i  h* \% ]/ g% X7 f" R# `9 G
1 V  `; G. O+ H: _3 E. D5 c/ e9 D) p首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
: e3 }$ U, A6 ?4 N
4 q4 ~. X# z+ a) _每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。

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

7 J$ w0 Y+ o; g" R; q这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
- B; P* N  I$ A
1 Y0 U" S9 D1 ~1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：
$ B$ ^. W4 o; n% Y4 ]1 ?
对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
' R. U+ a' l8 j! A9 g
对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。
- g/ C& P; E0 \9 B
对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。

6 i/ A+ d3 D" {0 y2 x6 K对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。
- e# r9 V/ `3 z- D1 H% K) A
2 S; U4 O* w& @9 {3 W( d0 h对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
( L1 c: s7 B$ T/ l3 I2 B
+ i( f. a  H3 m3 _" C, J总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

二、代码实现
2.1 Python 实现
以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
   
2.     if len(arr) <= 1:
   ! T5 @# J1 S+ A$ ^
3.         return arr
   " T: x5 t) ~5 {* s
4. 
   4 I& l- B; ~# X  z
5.     # 将数组分成两个部分
   
6.     mid = len(arr) // 2
   
7.     left_half = arr[:mid]
   ) V) H3 q5 S: q
8.     right_half = arr[mid:]
   
9. 
   6 P3 U& K! \5 C. z
10.     # 对左右两部分分别递归调用归并排序
    
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    ; w& m2 ?$ M' R. c, A. l. `& M. ]
13. 
    
14.     # 合并左右两部分
    
15.     return merge(left_half, right_half)
    2 [% K8 n" q4 M% i' m2 g& B: }
16. 
    
17. def merge(left_half, right_half):
    
18.     i = j = 0
    
19.     merged = []
    
20. 
    7 w8 r+ q1 S  D  t9 V" o+ |$ ~
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
    . |& k  e" t& ~( @* d
22.     while i < len(left_half) and j < len(right_half):
    1 `0 X/ ~' e9 h4 S  h0 f2 P, n! L
23.         if left_half[i] < right_half[j]:
    
24.             merged.append(left_half[i])
    ) H% N4 P9 X/ l
25.             i += 1
    
26.         else:
    
27.             merged.append(right_half[j])
    
28.             j += 1
    + u: [  _# c. _( p, `, i9 C
29. 
    5 W) G6 E3 m( ]
30.     # 将左右两部分中剩余的元素添加到 merged 中
    " Y- z8 z. k$ J, ^# R7 \: c
31.     merged += left_half[i:]
    $ I+ ?7 Q6 ~8 S
32.     merged += right_half[j:]
    
33. 
    5 X/ {4 n( X; }; f$ b2 p1 L% J
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):
   ) m( A  @- ^" Y/ _
2.     if len(arr) <= 1:
   ) @( A/ X" _0 I: O8 M
3.         return arr
   7 Y* Y2 w! L2 z# T3 z
4. 
   . k, e5 M0 c2 h. L9 `3 F7 b4 e
5.     # 将数组分成两个部分
   
6.     mid = len(arr) // 2
   # X7 I0 Z( W# J, s- F! s4 `* `6 s
7.     left_half = arr[:mid]
   
8.     right_half = arr[mid:]
   ; o4 c1 I' O2 W. ?) j9 d& h
9. 
   ( o+ y/ s0 x- Y# `5 F5 ]
10.     # 对左右两部分分别递归调用归并排序
    
11.     left_half = merge_sort(left_half)
    
12.     right_half = merge_sort(right_half)
    1 @' b* d7 k" l4 V$ e. t
13. 
    
14.     # 合并左右两部分
    . R2 X& R" N& X
15.     return merge(left_half, right_half)
    + ]$ V' K& }8 T0 [
16. ```
    ; N0 \* [4 l& y
17. 
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    $ L. D& r, j2 S

复制代码

merge() 函数

1. def merge(left_half, right_half):
   4 F- f* H/ K+ ?  i2 G. C
2.     i = j = 0
   
3.     merged = []
   8 @  n+ i$ h6 H
4. 
   . V3 F7 ~% y  T9 C3 R+ c8 |* y
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   
6.     while i < len(left_half) and j < len(right_half):
   : y6 i) o" C( ^+ f: b
7.         if left_half[i] < right_half[j]:
   
8.             merged.append(left_half[i])
   0 O0 {' l  `3 t' R
9.             i += 1
   0 T" d' d6 {. L! |# S
10.         else:
    
11.             merged.append(right_half[j])
    1 I/ q( z" j- t3 [) T; E* D
12.             j += 1
    
13. 
    
14.     # 将左右两部分中剩余的元素添加到 merged 中
    
15.     merged += left_half[i:]
    
16.     merged += right_half[j:]
    
17. 
    , z% q0 ]8 k7 U3 l+ \
18.     return merged
    ; s  K! m9 t1 h: S
19. ```
    
20. 
    
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

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

1 P5 t3 F1 P$ B0 D+ j% `判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

将数组分成两部分：需要使用 Python 的切片操作来实现，将数组分成左右两部分。

5 j" v. g' j- {+ M4 \+ x- r对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
7 f( N" t( L  R, g9 a2 v7 e. A
合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。
+ e' h/ t. D! W
5 E  g" M* {8 b0 U* c; C* h测试
在使用上述代码实现归并排序时，可以通过以下代码测试：

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() 函数进行排序，并输出排好序的结果。

5 r' [4 F5 y& r总的来说，这个实现是一种简单而清晰的归并排序实现方式，适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn)，但其空间复杂度为 O(n)，因为在合并过程中需要额外的空间来存储排好序的元素，因此在处理大规模数据时可能会占用较多的内存。
- K0 b3 I. D) r1 ?( [# G2.2Java实现

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

1. public class MergeSort {
   $ ^& P/ L% _9 F, h- {& S& `
2.     public static void main(String[] args) {
   # ~1 ?& P# s5 A# f6 X9 o! x
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};
   # [5 e! ^6 c# `: i4 X
4.         mergeSort(arr, 0, arr.length - 1);
   
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   - m7 I1 f! R; D0 C  E% [" t" i
6.     }
   1 Y2 k) j/ R8 k# v
7. 
   
8.     public static void mergeSort(int[] arr, int left, int right) {
   # P! x) }2 J) G
9.         if (left >= right) {
   & o) R4 _$ N: T: {6 N( @, h. t
10.             return;
    
11.         }
    1 b# g* t! N( b( ~
12. 
    
13.         int mid = (left + right) / 2;
    + @0 H0 Z' E) M
14.         mergeSort(arr, left, mid);
    
15.         mergeSort(arr, mid + 1, right);
    " m4 `. D! h- c* e! n" w" R6 i
16.         merge(arr, left, mid, right);
    - O( g7 ^9 N; ^5 t1 D4 w1 r, ?
17.     }
    
18. 
    7 a: w" }9 K& n
19.     public static void merge(int[] arr, int left, int mid, int right) {
    - ]( u2 M- m- v1 N/ U
20.         int[] temp = new int[right - left + 1];
    * k+ k; }" C! l/ _& [
21.         int i = left, j = mid + 1, k = 0;
    ! V0 }9 W' L* s& G% i
22. 
    , \, J, F9 n9 p" f! N
23.         while (i <= mid && j <= right) {
      S* A/ C& E3 K1 i3 |
24.             if (arr[i] < arr[j]) {
    
25.                 temp[k++] = arr[i++];
    
26.             } else {
    7 @. i+ {. ]: T" O% a; q& H
27.                 temp[k++] = arr[j++];
    
28.             }
    
29.         }
    
30. 
    5 s1 T5 y& @4 A7 J  {
31.         while (i <= mid) {
    
32.             temp[k++] = arr[i++];
    
33.         }
    2 p, V2 x3 ]% k9 S& n6 Z6 m
34. 
    & n. ^% M6 u: j0 |  w* F- @
35.         while (j <= right) {
    - u9 E. R" l. p( \" U; X( {
36.             temp[k++] = arr[j++];
    ) J, Q% j0 p1 u
37.         }
      b4 r) M* g7 @: U1 x6 G( x% F
38. 
    4 B* P% }1 R# }% ~
39.         for (int m = 0; m < temp.length; m++) {
    
40.             arr[left + m] = temp[m];
    
41.         }
    7 O7 u- V. q( m/ S! ~1 d
42.     }
    - t" @" T) D+ r, j0 i0 x2 [5 T
43. }

复制代码

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

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

* ]! s& b7 I- qmergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {
   1 B3 {6 M) l  @0 }8 [
2.     if (left >= right) {
   
3.         return;
   - t6 B  L$ @2 W+ u
4.     }
   4 M9 H( L: [4 K  w
5. 
   
6.     int mid = (left + right) / 2;
   . n: i* R6 }: M2 y3 E4 p
7.     mergeSort(arr, left, mid);
   # }2 D2 n: Q9 d" {8 P
8.     mergeSort(arr, mid + 1, right);
   
9.     merge(arr, left, mid, right);
   
10. }
    5 z/ l; T' n2 U
11. 
    / d9 J7 t1 e& W* o

复制代码

这个函数使用递归的方式对数组进行排序。
$ }0 |9 |, V( |! J+ p0 P
对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。

& e; w% y7 e* A$ U3 d最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
) y5 A' H; z3 k$ C* qmerge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {
   
2.     int[] temp = new int[right - left + 1];
   0 @0 }1 C1 Z& a- K6 p
3.     int i = left, j = mid + 1, k = 0;
   
4. 
   
5.     while (i <= mid && j <= right) {
   6 c( ^* c: p4 L4 p% @% Q: e* v3 O6 r
6.         if (arr[i] < arr[j]) {
   
7.             temp[k++] = arr[i++];
   . r# y' V: Z# P( `7 N
8.         } else {
   
9.             temp[k++] = arr[j++];
   
10.         }
    
11.     }
    ' O$ h7 g8 k* g! a2 X0 M+ n
12. 
    $ r" P: h% B6 }" f2 l
13.     while (i <= mid) {
    
14.         temp[k++] = arr[i++];
    
15.     }
    
16. 
    
17.     while (j <= right) {
    
18.         temp[k++] = arr[j++];
    
19.     }
    
20. 
    
21.     for (int m = 0; m < temp.length; m++) {
    
22.         arr[left + m] = temp[m];
    
23.     }
    
24. }
    : z. k1 r! _6 |& D

复制代码

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

合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 temp 中。

# z  B* n; q  ?) w最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
+ |; H& s+ d$ j- M& m
3 J/ ]% I2 A' c: Z需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。

6 R% b3 ]! Y$ r4 `: z这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

$ E0 e5 n) o# J( E2 Y- @
! v1 ~% E) w' _* R
. F% B" k4 F! h/ V9 O+ r0 D6 S7 P

. x, @0 b3 }8 Q0 k# V
) w0 n, Z# w+ R1 L1 t7 H1 `

---

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

Powered by Discuz! X2.5