- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
1 基础介绍
$ o: E z: g" ^$ y排序算法是很常见的一类问题,主要是将一组数据按照某种规则进行排序。. v0 f- G, c. k8 a) B0 C
6 K/ E0 k* G6 D# X' _以下是一些常见的排序算法:
0 ^0 ?' _% r, ~1 }, h @8 k
4 G8 V0 X/ q& n" {$ z+ W e冒泡排序(Bubble Sort)
4 _; E9 E$ y! z$ E1 U9 I/ g% ~2 p4 l/ f
插入排序(Insertion Sort)$ ?$ N7 j7 y/ k3 n5 K4 w
- L1 ?" {! M1 c! h+ r, T# A. ?5 n
选择排序(Selection Sort)
4 f3 m* d' }( P$ x' r4 q5 t7 k
- H0 W/ @& A; ^; v% I归并排序(Merge Sort)
4 S! o- W" T* N+ r# @% ^, Q, A2 n( o( i8 o. z$ X. }
快速排序(Quick Sort)$ {5 Z7 z. C3 H" O
& F. [; o( W. ?1 o9 a堆排序(Heap Sort)
: i' E$ |% u- Q! @* _" X
5 I: s4 \! d0 |2 P一、基本介绍介绍
1 G( V4 m6 e% L$ p8 y+ |' c2 p1.1 原理介绍! s4 G* ]; _4 f( f5 ]. B
归并排序(Merge Sort)是一种基于分治思想的排序算法,它将待排序的数组分成两部分,分别对这两部分递归地进行排序,最后将两个有序子数组合并成一个有序数组。它的时间复杂度为 O(nlogn)。
5 I( C+ h B% i$ i$ s/ }
5 d# E" D* d7 @6 K: d1 e: ?归并排序的基本思路是将待排序的数组分成两个部分,分别对这两部分进行排序,然后将排好序的两部分合并成一个有序数组。这个过程可以用递归来实现。具体的实现步骤如下:
+ t; P: u+ \4 K M& V* k3 }/ B' t0 V2 y ~
分解:将待排序的数组不断分成两个子数组,直到每个子数组只有一个元素为止。! x1 X5 Z* [# h f% N9 d/ |) _
5 P3 r7 I! M |+ w( g合并:将相邻的两个子数组合并成一个有序数组,直到最后只剩下一个有序数组为止。3 \4 L6 p3 q9 y! J9 G$ |
- U$ Z' Z3 M. G" y$ W合并的过程中,需要用到一个辅助数组来暂存合并后的有序数组。具体来说,假设待合并的两个有序数组分别为 A 和 B,它们的长度分别为 n 和 m,合并后的有序数组为 C,那么合并的过程可以按如下步骤进行:; r/ j2 |. B S( H$ s+ j, C. `
- \4 H. |" c" T8 g/ K
定义三个指针 i、j 和 k,分别指向数组 A、B 和 C 的起始位置。& d; K- t# o: D0 L
% f* y. v% B" {+ v4 P比较 A 和 B[j] 的大小,将小的元素放入 C[k] 中,并将对应指针向后移动一位。0 ^+ O7 N+ L% R. c5 [* C' W
1 d j+ [3 K- m! u' W; c. G+ w8 N重复步骤 2,直到其中一个数组的元素全部放入 C 中。
6 z1 m6 J2 B3 e
! K; ? y) d% S4 T% ] ]将另一个数组中剩余的元素放入 C 中。3 d- I% ^# P8 Z) X7 p/ m7 O
N/ O) c' e5 ]# ?1 R- y
归并排序的优点是稳定性好,即对于相等的元素,在排序前后它们的相对位置不会改变。缺点是需要额外的空间来存储辅助数组。
, F. D- r$ J3 i( b
( \% h- _$ s3 k" `& E- Z8 w原理简单示例 j/ M* g3 P) H+ p' }
以下是一个示例,演示了如何使用归并排序对一个数组进行排序:' f& n# x- q: M
; Q/ p4 n# W1 A7 C+ x
假设要对数组 [5, 2, 4, 6, 1, 3] 进行排序。
# m1 `* {3 i& q( B. A* v! |: {6 q
% ^$ @" @; Z! L3 \; U, i: }) L首先将数组分成两部分:[5, 2, 4] 和 [6, 1, 3]。
7 A! {5 G# s9 Y/ \; m
+ M B' {& }! o$ F1 ^对左右两部分分别递归调用归并排序。对于左半部分,继续进行分解,将其分成两部分:[5] 和 [2, 4]。对于右半部分,也进行相同的操作,将其分成两部分:[6] 和 [1, 3]。6 b+ l4 L. r; \) {* k l& C
* |; z3 L3 |: h6 t* d对于 [5] 和 [2, 4],由于它们的长度都小于等于 1,因此直接返回它们本身。对于 [6] 和 [1, 3],同样返回它们本身。
+ t4 _+ V7 @; L6 X; z3 T4 h$ e9 m( E, W* T- i
接下来将排好序的左右两部分合并成一个有序数组。对于左半部分,由于它只有一个元素,因此可以直接将其作为有序数组。对于右半部分,需要将 [1, 3] 进行排序,排序后得到 [1, 3, 6]。7 N0 A- D- d, A1 k; m/ z. E
]. [+ j$ E7 K
将排好序的左右两部分合并成一个有序数组。对于左半部分,指针 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]。/ c2 j W( D" N! q5 b" g
! C$ g, n9 A3 A7 J8 B, X因此,对于输入的数组 [5, 2, 4, 6, 1, 3],使用归并排序后得到的排好序的数组为 [1, 2, 3, 4, 5, 6]。
7 S( s1 G8 \; Q
+ d* o5 W p# k7 b1.2 复杂度 2 O6 h& h' o$ F5 X- g
归并排序的时间复杂度为 O(nlogn),其中 n 是待排序数组的长度。
3 Y0 l! K" o+ o2 ?" Y
# i' f" Y- ~# F! ]( R这个复杂度可以通过分治的思想来解释。7 u; P+ e* i4 o% i% Z2 |7 g
/ Z# X/ ^3 X- s: b1 v! ]. W% Q
首先将待排序的数组分成两部分,对每一部分递归调用归并排序,然后将两部分合并成一个有序数组。
1 ]# w- r. v7 r$ v1 H( ^/ L+ l( `" i+ b8 N2 J
每次递归调用都将数组的长度减半,因此需要进行 logn 次递归调用。在每个递归层次中,需要将两个有序数组合并成一个有序数组,这一过程需要线性时间 O(n)。因此,归并排序的总时间复杂度为 O(nlogn)。
- E. C8 s$ R* A3 H; S1 t" D% a! U8 d1 ^+ n; L. {1 Q" {
归并排序的空间复杂度为 O(n),其中 n 是待排序数组的长度。在排序过程中,需要使用一个辅助数组来存储合并后的有序数组。
; B3 u8 K- m5 ?6 P3 H
, d) [$ V) f# E9 c+ D这个辅助数组的长度等于待排序数组的长度,因此归并排序的空间复杂度为 O(n)。如果实现中使用链表来存储数据,空间复杂度可以降低为 O(1)。( y4 P& r& M9 o1 p+ v$ D
$ |0 Q1 B7 W* u: i/ `: I8 Z3 o1.3使用场景
3 c6 N0 U6 e5 e- w/ L归并排序的应用场景比较广泛,主要适用于以下几种情况:8 x: v! y) Y# w4 M" p1 U5 _3 ^
; |3 ?7 n# n: D8 A对于大规模的数据排序:归并排序的时间复杂度为 O(nlogn),相比于其他排序算法如冒泡排序、插入排序等,它在处理大规模数据时更加高效。
7 y/ [& m! n4 @: x1 \ N
1 l9 R b- D, N- q9 Y) E对于稳定排序的需求:归并排序是一种稳定排序算法,即对于相等的元素,在排序前后它们的相对位置不会改变。
2 Q5 q, N, i2 J5 E. u% @) U: [, \4 O& c8 J2 L$ i
对于需要保证排序稳定性的需求:归并排序是一种基于比较的排序算法,不依赖于数据的初始状态,具有较好的稳定性。
! Y" ]( x7 t: w0 w2 e; a* x3 h/ l. @ a# ^* I
对于需要多路排序的需求:归并排序可以轻松地扩展到多路排序,即将待排序的数组分成多个子数组,对每个子数组分别进行归并排序,然后将它们合并成一个有序数组。
0 r @, @( ~1 u7 ]/ L8 k8 I* r; ` t: @- J4 f
对于需要外部排序的需求:归并排序可以应用于外部排序,即在排序过程中将数据存储在外部存储器中,而不是在内存中。在外部排序中,需要使用多路归并排序来合并不同的子文件。
/ Q+ g! d" c' E
& Z R* S' s5 u! s2 z. @& A$ B总的来说,归并排序是一种高效、稳定的排序算法,适用于大规模数据的排序、需要保证排序稳定性的需求以及外部排序等场景。
5 D+ f+ f6 [" a8 `6 g0 J1 f- v* H- \7 r) a% a6 k U2 T0 N) F0 Q
二、代码实现
1 W8 E9 I6 N1 V/ ]0 N. T+ |2.1 Python 实现; n0 _; Y/ W+ A; ? P- g
以下是使用 Python 实现归并排序的完整代码:- def merge_sort(arr):5 @9 w: A7 _ X! S4 q1 n- v
- if len(arr) <= 1:4 h* s\" m1 Y0 e& |8 V/ c
- return arr
, Y8 L. D* _+ g9 z3 G$ y - - [2 n6 x/ x, j7 X
- # 将数组分成两个部分# }* Y; ?0 c; `& m1 t8 \7 G! n
- mid = len(arr) // 2 K4 |\" h+ S9 N) H
- left_half = arr[:mid]8 E\" o( C& j* l) M E! \\" ?% R
- right_half = arr[mid:]
% ?7 Z4 W, B7 V5 d3 l9 B w\" |6 t -
7 w) t; \: w8 S: k - # 对左右两部分分别递归调用归并排序* H7 p* N. ^6 G% V
- left_half = merge_sort(left_half)
0 l9 M4 S: O3 ]6 ` - right_half = merge_sort(right_half)
& j( u7 J4 W$ o4 S( B' y5 G -
7 {8 w' K: s7 F% e - # 合并左右两部分
, f: I- Z/ c9 i- X* o\" f+ c/ B9 m4 | - return merge(left_half, right_half)
+ m. i\" R: E) a! Q' b+ u5 m9 o - & \* B* C) J- ~
- def merge(left_half, right_half):
8 T! T0 C% Z, Y9 V- M - i = j = 0. E# X6 P4 I( g: c: d
- merged = []9 L4 ]; W: B1 Y
-
7 }$ |( T5 H) U7 u u. C# [) ` - # 比较左右两部分的元素,将较小的元素添加到 merged 中
8 `0 p5 x8 B: \* b. \( K - while i < len(left_half) and j < len(right_half):$ w0 T& o& a2 v- P/ |\" R
- if left_half[i] < right_half[j]:7 B) O* m+ L# n m* i! d% S
- merged.append(left_half[i])) `; S1 D7 v9 s6 f! ?
- i += 1; y3 _ p+ e1 Z) ]+ f/ n
- else:9 Y$ b+ _7 I- e9 k$ l
- merged.append(right_half[j])
& A0 b: O. @/ Y2 Y4 Y9 T - j += 1% A; v0 d) D: |8 Y3 R5 T* a+ f
-
& d9 ~0 z\" {, _7 G2 _8 F - # 将左右两部分中剩余的元素添加到 merged 中& f6 K9 ?( Q# y\" E8 i6 Q
- merged += left_half[i:]5 `, Z* ~6 Y# \# J
- merged += right_half[j:]# {0 c' P8 j# J) y7 A! ]
-
& a( ?8 J# X/ K - return merged
复制代码 代码讲解 这个实现使用了两个函数,一个是 merge_sort() 函数,用于进行递归调用,另一个是 merge() 函数,用于合并两个有序数组。下面对这两个函数进行详细讲解: merge_sort() 函数- def merge_sort(arr):& Q3 c8 T/ _ u* m( V0 r
- if len(arr) <= 1:
3 i( f: |8 r3 j2 J5 l. i1 F9 p - return arr: Q; V; T9 C, K' H& F
-
! p& y\" Z6 _2 l4 I! y - # 将数组分成两个部分
' A; p9 l+ u/ Q3 b; p - mid = len(arr) // 2
) }- |( E/ K( _ n - left_half = arr[:mid]( s/ @5 D+ Z* f* S8 X! T
- right_half = arr[mid:]. D( K' H& b0 [* C$ d
- 9 a+ B7 O4 d' g4 u' v+ p4 S& |
- # 对左右两部分分别递归调用归并排序
. B7 L2 x; E$ B1 E - left_half = merge_sort(left_half)
2 {\" G8 j% x! ^+ l. u- ]! u - right_half = merge_sort(right_half), q/ _5 \- J& u8 x5 J
-
8 O/ k' q' U% H\" _! Q - # 合并左右两部分' R* C3 c: m' J! ?# x5 q
- return merge(left_half, right_half)' r6 K, y+ u# m1 @+ M1 s* \
- ```
* R. Z! ?! F. A$ Z - 1 e: B8 R% }( V- h( @& z+ n4 p\" p6 m/ i
- 这个函数使用递归的方式对数组进行排序。对于输入的数组,首先判断其长度是否小于等于 1,如果是,则直接返回该数组。否则,将数组分成两个部分,分别对左半部分和右半部分递归调用 `merge_sort()` 函数。最后,将排好序的左右两部分合并成一个有序数组,并将其作为结果返回。需要注意的是,此处的 `merge()` 函数是在 `merge_sort()` 函数中调用的,因为只有在递归到最底层时才会对单个元素进行排序,而在其他情况下需要将数组分成两部分进行递归调用。
/ g. e5 k- I, W) m' _ -
复制代码 merge() 函数- def merge(left_half, right_half):
+ J. j: |/ a9 W8 k6 r - i = j = 0\" R, C+ C' t3 R. D1 Q H# H
- merged = []2 z! V# c7 ]4 t* M U2 Y
-
\" t, m\" U$ `, M. L( \# R; t - # 比较左右两部分的元素,将较小的元素添加到 merged 中
1 ]' c% X& H% V. t) M. f. h - while i < len(left_half) and j < len(right_half):
$ X3 B; _1 F\" G( C3 Z - if left_half[i] < right_half[j]:& ]5 ^! G& I/ _& G. A: a\" d
- merged.append(left_half[i])
. Y5 A. g- _1 z% {: ? - i += 1
# i$ K% B$ w/ |$ }7 E2 Q - else:0 a: Y4 V1 x& h7 [& X
- merged.append(right_half[j])
+ k% ~0 ~1 m' _0 ` - j += 15 I1 o1 [, f5 R2 X7 C) I
-
]. W# v7 L1 t2 f - # 将左右两部分中剩余的元素添加到 merged 中
& e2 r9 t\" O- Z0 H - merged += left_half[i:]
9 c8 w. g. b+ m' z - merged += right_half[j:]! [2 L) L ~; U5 v+ y5 o5 l4 w
-
2 ?; j# U. {$ A8 E+ u0 j - return merged
\" k1 H( Z$ S5 X- _( h9 k9 n - ```8 M( y\" E, }8 M! L
-
! \0 r- _2 r) o! a: Q - 这个函数用于合并两个有序数组。在函数内部,使用两个指针 i 和 j 分别指向左右两部分的起始位置,以及一个新的数组 merged 来存储合并后的结果。合并的过程中,不断比较左右两部分的元素大小,并将较小的元素加入 merged 中。最后,将左右两部分中剩余的元素添加到 merged 中,最终返回 merged。
复制代码 在实现归并排序时,需要注意以下几点:
, p% Z5 c( |3 N- @% k* N6 K- t3 a Q8 o5 x/ I
判断数组长度是否小于等于 1:这一步是递归调用的终止条件,防止出现无限递归的情况。
5 h1 Z' x2 ?+ @- |# s; X& j$ z+ B6 s! K
将数组分成两部分:需要使用 Python 的切片操作来实现,将数组分成左右两部分。0 b* t+ x5 L3 n, j7 V; M, V
: T$ s, w* n1 c4 z对左右两部分进行递归调用:将左右两部分作为参数传入 merge_sort() 函数并进行递归调用,直到数组长度小于等于 1。
8 u F9 `! L$ P! y; C6 q2 C& b, H0 V1 |5 ~3 ~: k) H4 A/ {
合并两个有序数组:使用 merge() 函数将排好序的左右两部分合并成一个有序数组。# P# O7 Z7 u9 G; _: m
/ }2 z: O6 A- A% F. |( U% U
测试
5 ^% _6 S- D2 t! t在使用上述代码实现归并排序时,可以通过以下代码测试:- arr = [3, 5, 1, 9, 7, 2, 8, 4, 6]: l0 A% D, ?7 y4 `- P; w) |
- print(merge_sort(arr)) # 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
复制代码 这个例子中,将一个无序的数组作为输入,调用 merge_sort() 函数进行排序,并输出排好序的结果。/ S% j, J8 C7 k9 j, [
# F8 T. Z# H) L/ q: T0 ?1 `总的来说,这个实现是一种简单而清晰的归并排序实现方式,适合初学者学习和理解。虽然这个实现的时间复杂度为 O(nlogn),但其空间复杂度为 O(n),因为在合并过程中需要额外的空间来存储排好序的元素,因此在处理大规模数据时可能会占用较多的内存。* K6 n9 V/ z: Z
2.2Java实现以下是使用 Java 实现归并排序的代码:
- public class MergeSort {
! ^% O3 W( M$ O, @+ y. H, H - public static void main(String[] args) {, t3 v3 X+ U/ F) Y' ~
- int[] arr = {3, 5, 1, 9, 7, 2, 8, 4, 6};1 z) [5 ]7 |5 a! s7 f7 `2 S6 r
- mergeSort(arr, 0, arr.length - 1);& [9 J; f. t# @0 m+ Q* N\" i
- System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8, 9]
; N\" Z; G! B# W# o$ C - }
: L0 _5 O# w6 M8 }8 h8 F -
* a# T; h: E0 q6 G. u - public static void mergeSort(int[] arr, int left, int right) {
\" \) S9 C0 _, f4 a. V5 w2 G9 N% `& x - if (left >= right) {2 r9 Z# I# e0 E
- return;; q9 L, `. b; f( D9 S
- }
# C3 o* B4 `( x9 }% P -
0 I7 M* a8 T& z6 e1 e\" e - int mid = (left + right) / 2;
+ q4 i4 T8 M) \2 Q - mergeSort(arr, left, mid);* G7 u7 x6 `! U) N6 | _
- mergeSort(arr, mid + 1, right);! {; S$ v- B, D( _; l! P
- merge(arr, left, mid, right);
0 ` d# Q2 t1 S0 ~: I# ~# Y - }
5 r/ x# M' @7 g& v! a - ( u. s+ W) d+ C4 D/ y2 D
- public static void merge(int[] arr, int left, int mid, int right) {+ S9 r' }# Q8 `9 C
- int[] temp = new int[right - left + 1];
) J; k7 b: W, N - int i = left, j = mid + 1, k = 0;
5 f# A1 Y# p( g9 Z1 o! Z8 P* g; C -
* O/ P4 Q\" Z$ [) \0 B- T - while (i <= mid && j <= right) {
4 t\" w; D* v7 `* K - if (arr[i] < arr[j]) {
- l: o1 G4 ?5 q - temp[k++] = arr[i++];
- d8 L9 g1 t2 S - } else {8 n7 `& B, T% h* `! L: v) m
- temp[k++] = arr[j++];. P: ~$ m e S- S0 T
- }7 A4 E; z+ [1 M) T
- }, ?) S: I% t0 w9 X
-
% b\" v) P. E% l9 F; p - while (i <= mid) {
* H3 P; ^6 u$ H8 I+ h! _( X - temp[k++] = arr[i++];
' {\" [# U1 I# }9 w6 w) Z2 b - }
3 }5 V' r2 p# E -
0 u9 A- }; S) c: d; w - while (j <= right) {5 M+ n$ X5 J1 R: B
- temp[k++] = arr[j++];) T; Z) e\" c8 y8 M. J0 Y4 N
- }
p. C( z- M2 u# v. a; @ - # y- b+ C/ t1 W' P& r
- for (int m = 0; m < temp.length; m++) {. [* f, W* |, I# Y+ l! N, I- B
- arr[left + m] = temp[m];
. }- n4 R0 N9 c' n9 | - }- n) y4 n9 e% G\" ^! Q7 e9 ~
- }
' M' {7 T+ G* o g5 z - }
复制代码这个实现也使用了两个函数,一个是 mergeSort() 函数,用于进行递归调用,另一个是 merge() 函数,用于合并两个有序数组。 下面对这两个函数进行详细讲解: % j" e' |8 E0 H V# s' M
mergeSort() 函数- public static void mergeSort(int[] arr, int left, int right) {
# d# U, V) W# F' ^ - if (left >= right) {
0 j6 O2 o6 c) P: m - return;
4 D# z; N: W+ @ N G - }$ `0 k7 |9 o K; x5 l
-
' d7 ~$ ]& W' i( k( S& E6 M - int mid = (left + right) / 2;% V1 m1 q1 Y$ H4 k
- mergeSort(arr, left, mid);' V: {6 ], a9 }
- mergeSort(arr, mid + 1, right);/ g# R4 x9 Z# W1 ?; s. R
- merge(arr, left, mid, right);7 M0 E6 {6 N2 C( S9 I
- }9 s+ T5 X* s% X2 S; J
-
, q3 i% T! ~$ f& P0 f, T -
复制代码 这个函数使用递归的方式对数组进行排序。 ~: S* [8 j7 M5 B5 {/ n
/ K8 {7 E7 Z3 X3 [- [& h! I对于输入的数组和左右下标,首先判断左下标是否大于等于右下标,如果是,则直接返回。否则,将数组分成两个部分,分别对左半部分和右半部分递归调用 `mergeSort()` 函数。
# ?( b r2 c# ^$ M, d4 F. U3 ]: l& j- w6 q' l" ?5 @! p
最后,将排好序的左右两部分合并成一个有序数组,并将其作为结果返回。需要注意的是,此处的 `merge()` 函数是在 `mergeSort()` 函数中调用的,因为只有在递归到最底层时才会对单个元素进行排序,而在其他情况下需要将数组分成两部分进行递归调用。, @5 G2 f! J$ r" i1 G, V5 t/ I9 x) v
merge() 函数- public static void merge(int[] arr, int left, int mid, int right) {) K4 n9 a1 A/ L/ C: `3 ^- t
- int[] temp = new int[right - left + 1];
& o+ v5 }* p, V+ Y% `. p - int i = left, j = mid + 1, k = 0;) n/ g5 [1 S( B) b' E
-
4 J1 o) m9 i/ q% r6 E0 R T9 S - while (i <= mid && j <= right) {
+ X% Q Q! G# _/ W7 l# b) x - if (arr[i] < arr[j]) {2 u6 [5 w) u4 S: |0 B$ Z: J
- temp[k++] = arr[i++];
1 U5 y$ K6 ^5 d( F( X\" n; S - } else {
! m* c\" |+ Z' w, A9 S% f {6 e - temp[k++] = arr[j++];
{* x' ~7 q9 _ H4 i* U - }/ o2 y; Z& Q2 w2 p/ w1 H2 C2 g
- }& r/ m7 C: V3 W3 b1 H$ t! v1 A% C
- S3 K! n; @! l, U: i9 o+ g
- while (i <= mid) { N q' M& k( B- X9 \
- temp[k++] = arr[i++];
' w' y' m X* r - }
5 F& d$ D& o- a! z2 a. w! s2 i) N5 r -
0 o* M* r) G5 r2 @ - while (j <= right) {3 O# {5 P' G$ }, X. y: Y/ M* u c
- temp[k++] = arr[j++];4 S$ o! F9 F. o8 ]
- }5 O6 J. Z, y6 K% E& o1 k
-
; |( J, [* y& @1 f8 V) X+ z% q - for (int m = 0; m < temp.length; m++) {
2 U( M0 e\" f* {; M: G! |. i - arr[left + m] = temp[m];
' H g( ~2 O- [* K8 X7 B/ ~ - }) N0 ]( u, D# W0 b
- }2 I1 E9 o6 C! T\" a
-
复制代码 这个函数用于合并两个有序数组。在函数内部,使用两个指针 i 和 j 分别指向左右两部分的起始位置,以及一个新的数组 temp 来存储合并后的结果。" t3 b' m, J1 p! B" `
) v, r1 H* ~% h: Q+ |合并的过程中,不断比较左右两部分的元素大小,并将较小的元素加入 temp 中。1 J, t1 S6 K/ w" x/ c) [
3 w3 X5 J& Q8 @. l* H+ j
最后,将左右两部分中剩余的元素添加到 temp 中,最终将 temp 中的元素复制回原数组中。% N1 @2 m: j- t2 s/ Y% j' o q1 s
. M4 F# |, @4 Z: K& g6 |* K4 x
需要注意的是,在复制回原数组时,需要计算出每个元素在原数组中的位置。
$ r4 L6 M( C$ d5 L. Z* d# ]% E! v) Z& W4 U1 h m) t
这个归并排序的实现是比较基础的,但是足以演示归并排序的算法思想和实现过程。当然,实际应用中可能需要对代码进行一些优化,比如可以对小数组使用插入排序来提高效率,或者使用迭代的方式来避免递归调用带来的额外开销。5 u% g3 U5 I8 P! K& Y
; t, ~% b( X. x4 A
+ X. [2 W% Q7 I: h/ h" J. B9 Y
! R/ D/ l6 c) r* ?
* {! \# U/ r! U. H2 ?4 B
$ c+ P/ J# @0 Z. h7 T& l
' R+ C/ ?. M' j7 `! F5 d: O* @( S8 u7 _
|
zan
|