数学建模社区-数学中国
标题:
神级基础排序——归并排序
[打印本页]
作者:
杨利霞
时间:
2020-3-30 17:02
标题:
神级基础排序——归并排序
6 {: K% o- t" R2 B0 G' R
5 d! y/ x5 i7 ]5 S! M
神级基础排序——归并排序
3 R0 ~ g- N' g: G6 Y
# f0 w& \( q X- }8 ~
归并排序的介绍
, c: G. T$ w3 e+ B" k o
- c6 E6 r) ]# X- X% {5 M+ i2 X
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
) J- Z4 I2 F! `9 E
概念
# K. [# i9 c5 `: f
; t1 x" D2 F& f& y" G
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
" A2 y) F+ J4 T9 J
核心思想
a- @2 P& j. T' O K* W
, b0 b1 e: Y6 |; o7 u4 _
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
: Q+ a- [" L$ d K9 h
) A( g! v9 c+ r, u+ e& x8 l
4 n7 ~/ G0 K3 U% S1 L0 \7 p
实现代码
: q: Q- G2 p3 O
import java.util.Arrays;
; x, `' |& j6 D- ~# Y W
6 r% l6 O$ Y8 l& Y1 ?
/**
7 @) q! R$ x8 j! v& `
*
@Author
god-jiang
, M; M( i. z2 w* j K
* @date 2020/1/13
9 G S1 {- m" a4 C: ?/ u+ `
*/
! J& o- N( N. A7 R. p' i, C
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
8 E, d# S3 q7 N p4 A# d
public class MergeSort {
6 p, H- F9 W" k/ c$ d8 Q
public static void MergeSort(int[] arr, int start, int end) {
3 y& {7 z+ W% R, j o- a
//分治的结束条件
1 W5 J, n, h# z% f% t9 W( y0 x
if (start >= end) {
0 `# Q- @( U/ g3 C. I
return;
& k6 `+ |& R: j" s; g5 K3 m7 l$ r
}
& j5 B, O! y! D2 J) F" D. ?
//保证不溢出取start和end的中位数
% x% z5 Y: J2 G- K# ^$ R
int mid = start + ((end - start) >> 1);
" [) ^7 ~" V5 H: V. m! T
//递归排序并且合并
. _+ l/ C/ a9 ]7 G: `
MergeSort(arr, start, mid);
) T6 a6 c1 p/ P7 U! v
MergeSort(arr, mid + 1, end);
5 I, \7 J9 p+ G! u7 H
Merge(arr, start, mid, end);
1 o, o# l5 t! ]8 f' ?# s& C! w
}
1 _/ B3 D& a6 z' f
2 S6 w" Z. J/ n! y2 f/ Y
//合并
B( P) d+ v# P" [: j6 ~
public static void Merge(int[] arr, int start, int mid, int end) {
3 {4 ]& _5 M* q, z+ G
int[] temp = new int[end - start + 1];
w9 s6 D3 |! `$ N
int p1 = start;
7 C4 n1 A/ G- V; C
int p2 = mid + 1;
1 ?, ^9 Y1 I1 Y) I; U0 j$ @9 J3 ]$ C% ^
int p = 0;
* O! e ?7 E1 \+ b; X" h
while (p1 <= mid && p2 <= end) {
; q6 ]8 e5 h7 D P
if (arr[p1] > arr[p2]) {
) o! a, ~& e8 }2 A* K1 g. k
temp[p++] = arr[p2++];
, ?/ ?% g/ G6 g- x) G
} else {
" N$ D' p& j; h' u& @) T
temp[p++] = arr[p1++];
: f5 S N& o3 b
}
- e+ {0 Q8 [& r, D% C+ o
}
3 b; z3 j+ k$ e1 H0 C4 ?% H
while (p1 <= mid) {
% ?% `! d! x9 x' Q+ T! A+ t- J: {
temp[p++] = arr[p1++];
" ?0 b$ G7 X9 o, d
}
- a `; t# f" a1 y: d7 b. p, Z3 z
while (p2 <= end) {
% @0 h! W( h7 Q5 j; h
temp[p++] = arr[p2++];
+ w2 | ]9 z9 x# ]# P4 L
}
8 Z7 s+ O1 s/ N$ I! s9 {8 w3 ]3 \
for (int i = 0; i < temp.length; i++) {
3 a1 ?& V" o. Y, }; ?
arr[i + start] = temp
;
; Q8 T0 F8 V9 ~) h. Z# ~/ B
}
7 L: \; C# a) Y1 ?# u7 _) }
}
# P* s! n+ }) A
4 g6 K: I/ Y3 U( I8 T
public static void main(String[] args) {
5 S$ g& Z8 W1 q6 k+ X" u. ~. R
int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
4 ?7 d9 l. Q8 Z- \6 v$ w: m
MergeSort(a, 0, a.length - 1);
, [4 w7 J0 I& n1 q: f k" B6 L% ]
System.out.println(Arrays.toString(a));
& j& Q) Q. }; U6 I) g0 Z% O
}
6 B& K% ^; o) K7 l
}
" Q, V5 q2 K- g2 ]% q' A4 j" j7 n
" E2 N$ h5 |- d7 r. Q: y6 H4 D
! G5 U/ A% W1 M% _( K) n
运行截图
7 ^& v7 Q2 f7 M5 K6 m
5 G8 _/ R% [9 `! A+ I
2020-3-30 17:02 上传
下载附件
(89.18 KB)
# D- }* e7 r$ w) i1 P5 B/ b
" E( l0 _8 m2 ?
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
( D- w* N& c! k
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
. T" k# j% u; J6 ^( h1 S! l
。
- ?/ {6 X# K, t ~( o% u
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
* U0 u- z1 w& B5 I# \
8 W; k9 e; f4 u- r) q; S
# ?! A; ~' l E/ j, r; D. W! n
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
