深入解析排序算法之——归并排序

2744557306

1 基础介绍
' S& J# u( K0 a排序算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。

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

& w" L' K) f) a; F5 R冒泡排序（Bubble Sort）

: D/ A6 s7 t" j$ a% I4 c3 h插入排序（Insertion Sort）
( B) [, D/ `2 o0 c% `9 G; s
* O+ @0 \- _6 Y选择排序（Selection Sort）

归并排序（Merge Sort）
1 Y' n1 x0 G8 x/ I" N
快速排序（Quick Sort）

+ `. {( }5 S5 a堆排序（Heap Sort）
2 N  U) @" s5 C+ m
一、基本介绍介绍
1.1 原理介绍
5 F8 |1 L8 X1 \2 @! Y归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组分成两部分，分别对这两部分递归地进行排序，最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。

归并排序的基本思路是将待排序的数组分成两个部分，分别对这两部分进行排序，然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下：

分解：将待排序的数组不断分成两个子数组，直到每个子数组只有一个元素为止。
2 d* q/ H* q* }# {3 ^, i! d
合并：将相邻的两个子数组合并成一个有序数组，直到最后只剩下一个有序数组为止。

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

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

" f2 W4 B5 P) t9 J比较 A 和 B[j] 的大小，将小的元素放入 C[k] 中，并将对应指针向后移动一位。
9 F5 G  G* g3 h$ i
重复步骤 2，直到其中一个数组的元素全部放入 C 中。
, v7 W. c. [/ o, S7 b
将另一个数组中剩余的元素放入 C 中。

: [' C) n, R: c9 i2 _/ {: z( B归并排序的优点是稳定性好，即对于相等的元素，在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
! q- }) ]/ B5 \* u5 `
原理简单示例
以下是一个示例，演示了如何使用归并排序对一个数组进行排序：

假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
: e: X) m3 w1 X& Y# _
首先将数组分成两部分：[5, 2, 4] 和 [6, 1, 3]。

对左右两部分分别递归调用归并排序。对于左半部分，继续进行分解，将其分成两部分：[5] 和 [2, 4]。对于右半部分，也进行相同的操作，将其分成两部分：[6] 和 [1, 3]。
, K! s( Y' E$ b% O! D# ~3 x
$ X  q8 w! l  d. s$ [. c, K9 Z5 ]对于 [5] 和 [2, 4]，由于它们的长度都小于等于 1，因此直接返回它们本身。对于 [6] 和 [1, 3]，同样返回它们本身。

/ d! q0 X" ?$ V8 f$ O接下来将排好序的左右两部分合并成一个有序数组。对于左半部分，由于它只有一个元素，因此可以直接将其作为有序数组。对于右半部分，需要将 [1, 3] 进行排序，排序后得到 [1, 3, 6]。
1 g3 x4 X9 ~# h' B5 M
2 k! k6 e6 _' D8 U" g( ~将排好序的左右两部分合并成一个有序数组。对于左半部分，指针 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]。

因此，对于输入的数组 [5, 2, 4, 6, 1, 3]，使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
! ~, w- I. e4 `( f. X0 s, p/ O7 K/ C
1.2 复杂度
归并排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的长度。

7 e. H5 p4 W% }6 S! r这个复杂度可以通过分治的思想来解释。
+ }. U. C& H5 S' ~) C
首先将待排序的数组分成两部分，对每一部分递归调用归并排序，然后将两部分合并成一个有序数组。
# ^9 J, W1 ?' p& K8 _0 Z% n& }* C
* Z2 s- A3 B8 C1 V* }; c4 T每次递归调用都将数组的长度减半，因此需要进行 logn 次递归调用。在每个递归层次中，需要将两个有序数组合并成一个有序数组，这一过程需要线性时间 O(n)。因此，归并排序的总时间复杂度为 O(nlogn)。
" C1 B0 k6 N$ {2 o( Y" @( f- }
" U* \. |& t; X归并排序的空间复杂度为 O(n)，其中 n 是待排序数组的长度。在排序过程中，需要使用一个辅助数组来存储合并后的有序数组。

8 J* ^) |% W% D9 o这个辅助数组的长度等于待排序数组的长度，因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据，空间复杂度可以降低为 O(1)。
+ `3 K2 {$ y" K1 `  I; f' M
1.3使用场景
归并排序的应用场景比较广泛，主要适用于以下几种情况：

- ?! V& o3 G8 a$ ~4 S9 K' p对于大规模的数据排序：归并排序的时间复杂度为 O(nlogn)，相比于其他排序算法如冒泡排序、插入排序等，它在处理大规模数据时更加高效。
! V& a& z& G" t& ?0 L5 I- N
3 Y# n& [) X7 c; w对于稳定排序的需求：归并排序是一种稳定排序算法，即对于相等的元素，在排序前后它们的相对位置不会改变。

7 q8 ?" U7 N+ \对于需要保证排序稳定性的需求：归并排序是一种基于比较的排序算法，不依赖于数据的初始状态，具有较好的稳定性。
$ ^! H6 R* k6 ^) H9 [- e- I8 W
对于需要多路排序的需求：归并排序可以轻松地扩展到多路排序，即将待排序的数组分成多个子数组，对每个子数组分别进行归并排序，然后将它们合并成一个有序数组。

对于需要外部排序的需求：归并排序可以应用于外部排序，即在排序过程中将数据存储在外部存储器中，而不是在内存中。在外部排序中，需要使用多路归并排序来合并不同的子文件。
& S6 y& K1 _7 ^) H# j+ `
5 y+ D) [. N) l  E( i" D总的来说，归并排序是一种高效、稳定的排序算法，适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。

0 H( b2 `# R3 j. z3 j+ |! R4 T二、代码实现
+ N6 c- k# O: b1 c4 o2.1 Python 实现
4 e& {5 S9 M$ C$ Q4 n+ [以下是使用 Python 实现归并排序的完整代码：

1. def merge_sort(arr):
     L* A\" ]# N' a! }, @7 z\" e) U1 |# E
2.     if len(arr) <= 1:
   # Z! Y- O3 p, ~\" r- L
3.         return arr
   & y\" t% u3 \, ~0 P
4. 
   8 J* l* `+ D1 B, V8 w
5.     # 将数组分成两个部分
   / K! R5 ^. z* z, z- A2 O: f
6.     mid = len(arr) // 25 a9 j+ [+ @- g! V4 Z8 Q- [
   
7.     left_half = arr[:mid]4 N1 H+ }1 `) p4 Y& D$ a& W
   
8.     right_half = arr[mid:]; Y: Q: u; G. e
   
9. 
   * G8 W1 v\" S0 O2 }0 l* ^
10.     # 对左右两部分分别递归调用归并排序
    + d) D\" N8 j: `- j- ~
11.     left_half = merge_sort(left_half)( P& C5 [2 A0 s9 l% _  ?
    
12.     right_half = merge_sort(right_half)# L: C\" \& `* b( j! w+ C/ d
    
13. 
    + w, r- B, J( ^' G5 A4 e; }
14.     # 合并左右两部分7 u\" f3 @5 `1 C. K
    
15.     return merge(left_half, right_half)
    # u  z, H0 E\" L& T\" k
16. $ A$ ]9 |8 q. d- e& O& E& g) i
    
17. def merge(left_half, right_half):; h0 d: {- d, k
    
18.     i = j = 0
    ; i# z1 P/ W* h* k8 J\" N
19.     merged = []% A: @8 A7 x6 P% c/ v( [
    
20. 
    7 D' h/ u& O  E% @  J: I
21.     # 比较左右两部分的元素，将较小的元素添加到 merged 中+ [- l9 L1 s+ w# L
    
22.     while i < len(left_half) and j < len(right_half):3 O9 {( D; u3 y% t( Q6 W
    
23.         if left_half[i] < right_half[j]:
    . ^1 S$ v# Y3 Q2 g\" [
24.             merged.append(left_half[i]): {- Z! u5 d0 }' s3 W0 M
    
25.             i += 1
    % I; E5 J) I: F( Z2 r+ x
26.         else:) O) ?! g8 U5 W+ t
    
27.             merged.append(right_half[j])3 Q' B6 ~0 H* b+ N
    
28.             j += 1
    + a+ U' d$ Z3 M; D, E. p
29. 
    8 I! x\" Y* Q% N  y
30.     # 将左右两部分中剩余的元素添加到 merged 中6 a& ^! v2 t* ^+ n/ {0 _
    
31.     merged += left_half[i:]; s8 }/ i! U, a
    
32.     merged += right_half[j:]
    ( D6 H9 w- ~+ C5 K
33. $ G9 J/ z$ `3 e3 I
    
34.     return merged

复制代码

代码讲解

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

merge_sort() 函数

1. def merge_sort(arr):+ i7 X& c5 [( M; {
   
2.     if len(arr) <= 1:
     H* J: T/ n0 j' o, ?6 E1 k
3.         return arr1 w6 s- ^) J7 j; S1 D
   
4. 
   ( O/ K: G9 z; L; x
5.     # 将数组分成两个部分
   : w  o; r\" D! g
6.     mid = len(arr) // 2! K+ d\" P- ]: K2 r( I: `, }
   
7.     left_half = arr[:mid]; b' }; l\" j& c
   
8.     right_half = arr[mid:]# w& d! n9 i0 _9 u* L0 D
   
9. % x  r+ W\" ^- \( b) B0 R) b
   
10.     # 对左右两部分分别递归调用归并排序: I! M5 z& t- @# D
    
11.     left_half = merge_sort(left_half)4 z% D0 t\" F\" r( G  U
    
12.     right_half = merge_sort(right_half)
    ) W3 t6 D7 ~2 G
13. 8 P# }, K\" J1 B3 u\" S+ @( J
    
14.     # 合并左右两部分9 K* l\" q, p. M+ b# j' Z
    
15.     return merge(left_half, right_half)9 m, k& V. O3 f1 n6 x+ S- {
    
16. ```  w! x5 |6 l0 ~% s5 k
    
17. 5 m, M- [: R9 v7 x% i9 ]% d
    
18. 这个函数使用递归的方式对数组进行排序。对于输入的数组，首先判断其长度是否小于等于 1，如果是，则直接返回该数组。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
    5 b, r  [1 k4 y* f% D9 `

复制代码

merge() 函数

1. def merge(left_half, right_half):
   ! K; \0 l. e; q4 Y. L$ u* M' t
2.     i = j = 0
   . U' T0 C$ r3 W5 \- g) u
3.     merged = []4 J\" D2 L; |+ r7 c
   
4. 
   4 e$ g+ G' T, m
5.     # 比较左右两部分的元素，将较小的元素添加到 merged 中
   ' E/ N  H2 a/ @
6.     while i < len(left_half) and j < len(right_half):% p7 }* M6 J6 h7 _/ a
   
7.         if left_half[i] < right_half[j]:# Q5 A; q1 S! A4 ?
   
8.             merged.append(left_half[i])
   : T' y4 @- j7 u
9.             i += 10 x- g9 c* n! H4 b/ F3 V
   
10.         else:
    : p$ _9 v( _( K, x* x; I
11.             merged.append(right_half[j])1 Z5 T\" M\" y/ X6 }\" l! Z
    
12.             j += 1
    ( X9 M2 K) f) J2 {. b
13. 
    - }& h% |; d9 i4 Y5 L
14.     # 将左右两部分中剩余的元素添加到 merged 中! K, S. c: D& l; B* U: @2 `! e
    
15.     merged += left_half[i:]$ J4 O( A\" Z. E9 H$ m6 \$ Y
    
16.     merged += right_half[j:]
    ; ]& c. m6 K' j6 l- B) _
17. 1 @2 I# _/ Q  n
    
18.     return merged/ E) D; b. C9 J3 k9 X
    
19. ```1 P- r- z1 T1 O- v; C1 U4 ?
    
20. 
    2 i+ r* r8 K  M# n; c
21. 这个函数用于合并两个有序数组。在函数内部，使用两个指针 i 和 j 分别指向左右两部分的起始位置，以及一个新的数组 merged 来存储合并后的结果。合并的过程中，不断比较左右两部分的元素大小，并将较小的元素加入 merged 中。最后，将左右两部分中剩余的元素添加到 merged 中，最终返回 merged。

复制代码

在实现归并排序时，需要注意以下几点：
9 c9 C% c5 F! _- J
判断数组长度是否小于等于 1：这一步是递归调用的终止条件，防止出现无限递归的情况。

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

对左右两部分进行递归调用：将左右两部分作为参数传入 merge_sort() 函数并进行递归调用，直到数组长度小于等于 1。
% e5 |/ T0 X% v2 i- x
6 b. P% |' |1 M( E  q6 c, N合并两个有序数组：使用 merge() 函数将排好序的左右两部分合并成一个有序数组。

  b; a, l" F( ^测试
7 P. ?- f7 G$ A  w# \  A+ _在使用上述代码实现归并排序时，可以通过以下代码测试：

1. arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]  `/ C$ _+ j* R+ H& N) S# ~
   
2. print(merge_sort(arr))  # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]

复制代码

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

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

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

1. public class MergeSort {9 Z  c/ F$ A\" F2 P: Q+ C+ ~  G
   
2.     public static void main(String[] args) {
   ) S\" A' m/ z- d$ a
3.         int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};: [6 W\" ?+ J  F. V( B2 m9 d
   
4.         mergeSort(arr, 0, arr.length - 1);
   \" p8 l3 |8 g) Z9 V- x
5.         System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
   * A1 H, H6 t7 K- ^4 v2 Z
6.     }3 [0 j& a. Z# U
   
7. 
   ( ~/ ^$ i8 I1 Y- n/ E8 m
8.     public static void mergeSort(int[] arr, int left, int right) {/ k! ]$ Y7 I' R0 s1 E! u5 L
   
9.         if (left >= right) {
   0 j\" w4 e- E, A& E/ L! e7 p
10.             return;$ c4 m- n6 \$ Q! O3 S5 S9 p
    
11.         }
    & t0 C7 i' i( S3 z
12. 
    0 J# s, t5 k: a
13.         int mid = (left + right) / 2;
    $ k2 X. S* c9 Y6 m1 E
14.         mergeSort(arr, left, mid);
    0 R) C4 y& t) {
15.         mergeSort(arr, mid + 1, right);
    ; c+ W8 D1 N. o1 J
16.         merge(arr, left, mid, right);. b9 o+ o5 h* E- y3 U& _  \6 j5 a
    
17.     }! l: e9 b2 f7 K+ S\" }
    
18.   L0 H' ?5 J, U/ e* ]
    
19.     public static void merge(int[] arr, int left, int mid, int right) {
    ( i7 X+ |- U\" n& f# _1 \
20.         int[] temp = new int[right - left + 1];. h$ q( Q$ ^/ z$ f5 v
    
21.         int i = left, j = mid + 1, k = 0;1 I7 L8 ?& Q- I
    
22. 9 K( z. l$ T) j2 m' D5 n
    
23.         while (i <= mid && j <= right) {
    , u- }1 u3 [& e3 X
24.             if (arr[i] < arr[j]) {0 k% N- b) [: D5 K( l\" H+ v
    
25.                 temp[k++] = arr[i++];
    # h# x- k  v3 p, ~$ o( z
26.             } else {
    : B& |- ?7 ~2 G% N# ]% P+ V2 N
27.                 temp[k++] = arr[j++];
    0 y, Z7 H9 J9 H, ]( u3 X3 R
28.             }
    5 x+ R( p% q( R9 h& s
29.         }
    8 p5 ^7 N9 y; T* y& p) d
30. ; k6 s/ f, y  }7 a2 J
    
31.         while (i <= mid) {; ^$ q\" T7 f# {7 g. z
    
32.             temp[k++] = arr[i++];
    9 b! B9 h3 V: u+ x5 ^
33.         }
    5 n: ^1 A# M6 W+ S0 A
34. \" f6 `  N; r; K! p! b- u8 [
    
35.         while (j <= right) {. x: C# z# |/ Z% F
    
36.             temp[k++] = arr[j++];
    ! [% g' k) s! T! t+ O0 E2 e7 b
37.         }
    . t0 j. Q1 l3 v3 c, m8 h
38. $ i! J  F- m0 `7 w$ A* J
    
39.         for (int m = 0; m < temp.length; m++) {
    : F: l4 [3 H9 R+ F( w6 U4 J
40.             arr[left + m] = temp[m];1 F' O8 S' {+ I: X
    
41.         }& _5 r6 O; S2 O* [3 |: i
    
42.     }, I  O+ c) |: U1 A\" ]5 B
    
43. }

复制代码

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

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

mergeSort() 函数

1. public static void mergeSort(int[] arr, int left, int right) {8 l6 [5 n6 g) ~
   
2.     if (left >= right) {0 L, L. r& u/ G! L; F
   
3.         return;# |. g: I& r7 u& c& a! t7 d
   
4.     }
   / e! {6 f+ f  u\" Z; b9 [
5. 
   ' l, c3 E\" Q* v$ s& g9 P
6.     int mid = (left + right) / 2;
   3 k1 w+ X$ b: b6 j% V9 X, ?( y
7.     mergeSort(arr, left, mid);
   + k& ~) F8 \# @
8.     mergeSort(arr, mid + 1, right);\" b% G  w* e# ^+ ^6 s9 L
   
9.     merge(arr, left, mid, right);
   ! I. O+ E, M: l) E0 v* R
10. }& A% X/ X; |9 r7 |+ l& ?- w' T
    
11. 1 L& n( @) V3 l5 [
    

复制代码

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

1 S% I" Q- P8 G  e; L, V; ]对于输入的数组和左右下标，首先判断左下标是否大于等于右下标，如果是，则直接返回。否则，将数组分成两个部分，分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
' m) L2 c% Y% d
8 p' s2 d/ {5 G最后，将排好序的左右两部分合并成一个有序数组，并将其作为结果返回。需要注意的是，此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的，因为只有在递归到最底层时才会对单个元素进行排序，而在其他情况下需要将数组分成两部分进行递归调用。
merge() 函数

1. public static void merge(int[] arr, int left, int mid, int right) {0 _9 `7 }4 S2 J- ]- I% q0 }9 ?
   
2.     int[] temp = new int[right - left + 1];7 u: \# j) G  Q: }. ~\" q
   
3.     int i = left, j = mid + 1, k = 0;5 y' I8 r6 u9 |# r) {7 }' V
   
4. 
   $ K4 f5 D9 N. ]- p2 M2 x8 S/ m
5.     while (i <= mid && j <= right) {\" z5 e6 |/ q; n3 ~4 d8 F\" c
   
6.         if (arr[i] < arr[j]) {4 E# h4 [\" [+ J4 x3 K
   
7.             temp[k++] = arr[i++];8 U) @: v3 L# _1 v- L
   
8.         } else {; i\" g) H0 R9 ~
   
9.             temp[k++] = arr[j++];
   / R' Y( o* Q  O7 i- T$ n5 R
10.         }2 u6 n0 ?( g  o
    
11.     }
    ; \7 r, E5 H0 }6 A: X- r. T
12. ) U' B0 u5 F5 x& T! N) D( l' `/ t, t
    
13.     while (i <= mid) {8 Z  [( W\" c; _: b0 i( \/ l
    
14.         temp[k++] = arr[i++];! o! L- Q- v5 T0 F
    
15.     }0 |7 g6 N& j9 n& P
    
16. 
    4 k2 A$ i' l2 Z. Q; l' e8 f
17.     while (j <= right) {
    % h* ^9 Y3 }1 Y- G
18.         temp[k++] = arr[j++];
    2 v1 Y\" ~$ M3 U* d, @, `: F
19.     }6 Y4 Z5 X\" ^\" w( Z
    
20. # g! w& B( M( `: D
    
21.     for (int m = 0; m < temp.length; m++) {) b: B8 |. z7 R* S2 J7 r' a% s
    
22.         arr[left + m] = temp[m];# v4 M5 W3 a: J- u. E  W, L
    
23.     }
    + j& Q3 B5 c# \& A, o
24. }# E5 V% r8 U: j, T! o
    

复制代码

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

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

最后，将左右两部分中剩余的元素添加到 temp 中，最终将 temp 中的元素复制回原数组中。
8 f9 Z% z- w8 {, c
( ^6 X0 c# @  o) b8 H! ~需要注意的是，在复制回原数组时，需要计算出每个元素在原数组中的位置。
$ F1 b1 M7 Z* Z8 Y
# T+ i/ a& l5 @2 V# E8 N2 x' [这个归并排序的实现是比较基础的，但是足以演示归并排序的算法思想和实现过程。当然，实际应用中可能需要对代码进行一些优化，比如可以对小数组使用插入排序来提高效率，或者使用迭代的方式来避免递归调用带来的额外开销。

# s' D) _' e, @! b* K1 y1 X

( I3 [4 d# K  n" h; i$ x3 M; H+ m2 f

9 T& Y" r' p2 ?+ t
4 g! h+ D- M) w" ]$ U$ W6 `
5 w6 t, a. S1 @' \- s