数学建模社区-数学中国
标题:
神级基础排序——归并排序
[打印本页]
作者:
杨利霞
时间:
2020-3-30 17:02
标题:
神级基础排序——归并排序
) H! J k, a* y
. G7 q/ G4 B) |- z
神级基础排序——归并排序
! U" X: {! N# P4 h5 v
9 _9 @/ `$ ^2 a4 n/ O! I3 x
归并排序的介绍
! R0 j$ C# {) p
1 ]# e+ u) P( l, a( R! ^
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
: f& I4 N% a% N
概念
% P8 L% K M$ Z! I' m* W! `
& w$ ~! D0 d" G+ J( B0 N( v
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
+ }) L+ s: s R6 Q" M' S v. X
核心思想
9 S5 V9 y2 m; W$ `4 v3 D
9 }' `1 B4 Q! o3 q4 d! Y
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
$ \2 }- S' t: ]; u7 t( N
! w0 B) l- e1 F0 |
2 s: I' y, r6 ^2 @
实现代码
( z( x% H: @8 S: f
import java.util.Arrays;
; X. A2 o8 ], h3 z, O7 {
, z8 B& A! x' ]+ g6 e
/**
, `1 `* l" A5 W: b) e) X
*
@Author
god-jiang
6 ?$ m& Z, `3 E8 u3 j% y q) H, @
* @date 2020/1/13
4 {% Z0 @( y# _, u6 q& R% T7 K
*/
7 l- f; M. \9 U& a
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
/ L* A( R- o& }. ~/ z
public class MergeSort {
+ X6 `% \' t4 D4 t) u5 }4 X: f
public static void MergeSort(int[] arr, int start, int end) {
- ?1 u/ m7 Z. X9 E6 v* G
//分治的结束条件
! V8 G# A3 P8 w2 Q. c- p
if (start >= end) {
* y8 d; t- K8 ~0 ?2 ]4 \6 l
return;
# b$ z. j( U1 a+ m3 v1 j( h' i& r
}
/ R; n; R4 h9 k
//保证不溢出取start和end的中位数
0 N) m! h( N- Y5 p7 n4 o
int mid = start + ((end - start) >> 1);
D6 j5 U3 ]0 B" n9 K( ?
//递归排序并且合并
+ o% y' W( q" M- R1 D) ~3 |
MergeSort(arr, start, mid);
6 k* V3 S' T3 Q& J6 s' F, _$ A
MergeSort(arr, mid + 1, end);
1 W6 p1 W" h( \0 R
Merge(arr, start, mid, end);
6 |! U- u* j4 H& g) x7 A
}
# ?- j4 ^- x8 P- n
% c1 g: C- o; g% z O: X7 x5 y
//合并
U& q9 ]* N. Z
public static void Merge(int[] arr, int start, int mid, int end) {
. s, x* z; `3 N% P, Q! I
int[] temp = new int[end - start + 1];
3 g5 G2 d. \- E6 r4 _
int p1 = start;
& G3 P1 m$ U$ X' q; S- d' d
int p2 = mid + 1;
3 ~8 |) N8 [5 _$ Q
int p = 0;
8 w/ s2 P9 h% E0 E; X
while (p1 <= mid && p2 <= end) {
( B% l. d( X) K
if (arr[p1] > arr[p2]) {
$ l( C; R. e4 m% a
temp[p++] = arr[p2++];
) x T Z: w; S2 b! @' O1 }
} else {
2 i( m5 D0 S3 i) q1 F) u
temp[p++] = arr[p1++];
& a+ d9 W$ V: p: ?9 z
}
$ B# e% S7 }' f2 ~/ K
}
- F" _0 b& f7 `+ q$ `
while (p1 <= mid) {
$ D- h6 W6 r' G3 H( P2 G8 U4 G
temp[p++] = arr[p1++];
$ C; \6 l( ~9 k, p
}
& z) z' J8 t! I
while (p2 <= end) {
8 ]# t/ w. @# |" y$ @+ q6 W
temp[p++] = arr[p2++];
+ g; K! \% \4 e4 D7 u
}
0 S8 W( b6 t5 C% C ^* @. z
for (int i = 0; i < temp.length; i++) {
) n5 Q$ `1 X: X, p2 P# M" r; @
arr[i + start] = temp
;
1 a" ^ \6 q5 Z; [" S
}
! r% d$ q5 S7 O* y) V& T
}
7 S& b1 k6 M0 Z+ _
" i1 F3 v/ @' H) ~ B, O
public static void main(String[] args) {
9 Y! m5 v& \) `& m- h% ?
int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
& D/ K" D. J8 ^
MergeSort(a, 0, a.length - 1);
/ z' w; W5 Y# D J/ c
System.out.println(Arrays.toString(a));
- W# n1 o' t! l8 v* u7 ]
}
, |8 O1 h0 _6 R( U& c3 r
}
4 H3 k% B+ n z, \5 b
: [$ e4 m q0 v* t$ w* I
% n5 ?- ^7 n, I' ^7 G7 ^
运行截图
7 W+ |2 S+ x$ K
# U0 E) q2 ]) c1 t ]! d
2020-3-30 17:02 上传
下载附件
(89.18 KB)
* g, p m0 _+ C
2 p" J' i8 i- E" o
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
5 P$ p; v) W& ~+ [
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
- F) l6 e1 V- g/ M# M0 O
。
. `6 J6 X5 z2 C+ O3 F5 U4 x' D2 A
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
/ ^3 ^/ O8 }, f8 L; }( V
0 N9 Z) |1 ?' U i5 w: Z
& \, V) w2 _) M) |5 D
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
