数学建模社区-数学中国
标题:
神级基础排序——归并排序
[打印本页]
作者:
杨利霞
时间:
2020-3-30 17:02
标题:
神级基础排序——归并排序
0 P( Q8 y' Y# G5 t c
_ z e* k- ^7 E7 z
神级基础排序——归并排序
/ b" D/ b* B% D/ c3 j/ R5 u$ e1 ]0 ]
) G% w( P& E8 F
归并排序的介绍
* I8 l1 F% {; f, ~" ~
5 l8 K ^9 b" g6 z1 ?. C
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
7 P/ P9 I3 C: _5 K9 S6 w
概念
' O$ Y* a4 n1 ~* ]. c# l
& {7 @1 X- F- H9 B
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
" i9 N/ @4 b: a6 J
核心思想
8 `1 l) W( W7 ]
3 ~3 Z0 s4 P7 t! w7 k
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
9 S# Q/ p3 N7 Q5 t
% t) x8 ~/ N4 y8 F/ d/ J
/ d& I" T( [) |% J8 d
实现代码
; D1 u& D) o$ t# L
import java.util.Arrays;
# u% M9 j9 [- c3 \+ t9 q9 K& V; C h4 t
5 O! d& `+ g( D( v6 K% z
/**
6 ~' Q; C7 o& l; x1 F, Z
*
@Author
god-jiang
$ P2 ?1 l( Y. ]0 f, U
* @date 2020/1/13
, H, @7 T: c3 R6 `. \
*/
$ w6 I2 R- w% j5 P6 E3 Y
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2 |1 ^- U8 j6 J l. A# r
public class MergeSort {
9 g* o5 Y0 v1 X; U0 J, f
public static void MergeSort(int[] arr, int start, int end) {
; Z8 K, {( d, f, F
//分治的结束条件
3 p6 J* p, p) v7 ^8 f1 x
if (start >= end) {
6 n+ [) O/ I4 C$ d/ L) h: w% F
return;
5 H0 s' F. `0 V
}
( v1 b+ o5 H6 H' H) D8 \
//保证不溢出取start和end的中位数
1 y) X3 s! ? ~ I7 Q
int mid = start + ((end - start) >> 1);
e7 U: d8 _, \5 D4 m+ r3 a0 `
//递归排序并且合并
$ a( ]. H6 E e
MergeSort(arr, start, mid);
7 S1 Z; L7 I0 v5 s5 A1 o1 g- X
MergeSort(arr, mid + 1, end);
1 `! E9 p( a( o$ `* v2 J
Merge(arr, start, mid, end);
1 L5 y/ c1 L, L6 Q
}
: O8 |1 b, X5 e! N: Q
Q x2 K. }; @/ o0 N% C- n
//合并
# e; }7 L" F. V6 r7 g
public static void Merge(int[] arr, int start, int mid, int end) {
! w7 B- k0 U+ R; z! ?8 q
int[] temp = new int[end - start + 1];
& _; t8 t( ~# }3 F7 G- ^' B
int p1 = start;
n2 y! H$ f$ u1 {" T
int p2 = mid + 1;
( T2 w3 h, U4 i! i0 o! d" J
int p = 0;
- X" D3 i( A4 ?+ Q
while (p1 <= mid && p2 <= end) {
8 k) |$ Y4 V8 D
if (arr[p1] > arr[p2]) {
: {* \+ ], H' M( n2 [* L
temp[p++] = arr[p2++];
9 H6 V+ P) ~1 Z+ t7 G9 p
} else {
. C2 [- A, T7 [& m! e+ x
temp[p++] = arr[p1++];
$ Y9 f0 E( K1 l m( s
}
9 a; ^& f2 k0 V" A6 M" c
}
1 c3 `9 F0 L% e& V
while (p1 <= mid) {
& D; |% }$ y$ a+ I
temp[p++] = arr[p1++];
3 g* b4 Y3 a8 v/ [8 B
}
/ t: K( g# k* j1 D* P
while (p2 <= end) {
# j. B' v; u& L4 m; G9 v: d
temp[p++] = arr[p2++];
, F6 c, E$ v+ L. [' U$ B9 O1 E
}
2 w6 F& G. z9 V8 O& O* L
for (int i = 0; i < temp.length; i++) {
- `- ^# v+ \ k6 _# h+ J2 D
arr[i + start] = temp
;
2 P& A$ V' h2 K; Z! [3 S
}
* \& S2 ^% g% |2 F7 s2 I
}
+ D( ?, [2 r0 n6 X
5 Y2 g) Y8 c. M0 y
public static void main(String[] args) {
& b5 t* E! m6 r. l l8 _4 |
int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
# K* P/ I: j6 ?) Z- t* P; l
MergeSort(a, 0, a.length - 1);
! \/ H3 e' @9 B6 |9 N$ V8 ?0 W& K2 t
System.out.println(Arrays.toString(a));
- Z) @0 x! f" x$ j- c/ m$ n7 v6 k5 m) k
}
( P' O: W+ }9 o
}
; Y+ {9 e6 g' \& Z7 B
7 _0 r6 O; q/ A- d( @, i5 q. J
7 P& N) B' D) l5 v0 j. ~
运行截图
6 P3 J' j! R. V
% a: _& x% U9 Y0 J3 D" _
2020-3-30 17:02 上传
下载附件
(89.18 KB)
6 p; _ z2 t% F# k
G7 Z5 P! l. y3 \/ P
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
( n) Y) i7 z0 R
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
( f, W7 N8 c, T& X! ^8 z* A* ]
。
% _8 w9 s; B/ k# ~* Z+ w b* ]& S0 T z' A
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
6 C O' V, z( m! [9 ^# W
7 K3 c( h, I# q
7 u9 H8 q: i) F$ V, N
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
