- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 565551 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174888
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
$ y5 l: h: d0 l+ f2 Z& y& s, K5 i% d+ i. M/ d" ~
神级基础排序——归并排序
$ @$ m, v, R! b; }" ^
* D$ S) W4 ^! d( B3 B3 a归并排序的介绍2 g) v {4 Q4 I$ f) w! g) T- f
$ f2 R2 H/ k) N6 L, m4 G: @
归并排序(英语:Merge sort,或Mergesort),是创建在归并操作上的一种有效的排序算法,其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。+ R* U: B. e3 F) c& q9 o
概念, y- B4 t5 I5 k/ j5 C" \
2 u$ h" ^, @9 `- q Q& T* r
是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。7 x) I$ ?' E* m! w
核心思想' w( x$ j- {* x
/ Z6 ]# p4 Z \( X% E5 ]! d0 l( ?将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。5 {/ w) I# Z$ e
* f3 h! {% f. T. r
2 n$ T% C! n) X1 t4 ]0 ^
实现代码
) a* V0 A1 O% l% B# @import java.util.Arrays;* b) a G7 K1 g+ {
) ^; _ Y1 V5 Y
/**
+ _2 P! v+ @; V# q6 e. W* M. f0 o * @Author god-jiang. P' m0 E. T$ u( }* N7 ?) L# N
* @date 2020/1/13: O" S2 E% n0 C1 L6 {
*/
+ C$ N# w7 {; i! E7 D//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)) p# f1 _& _6 n& `* `9 {$ B
public class MergeSort {; f+ _# T! p+ t p
public static void MergeSort(int[] arr, int start, int end) {& z1 G7 Y$ D0 O$ {+ ~* V, B
//分治的结束条件3 G k8 `: X2 D
if (start >= end) {
c4 F) S: w2 @4 v+ l! C) ?8 \ return;
% S8 C* _. }3 y& D }8 }: i! `* `9 Y/ p h( c
//保证不溢出取start和end的中位数! O; H4 D: F1 B
int mid = start + ((end - start) >> 1);7 S: Z* y9 B+ K! W
//递归排序并且合并" Z3 D4 \( t! b! T( w9 o" ]5 V% @
MergeSort(arr, start, mid);7 a# U3 P, A3 t/ Z$ X7 s% i
MergeSort(arr, mid + 1, end);7 l! z: k- L" P5 W$ A! E; ~
Merge(arr, start, mid, end);
4 ~/ R D1 ?& E7 n: j. | }
& J5 g8 `( a- s: W
' J+ ?% b0 b \" k, }& W9 p //合并 D& D' B2 p& N* w
public static void Merge(int[] arr, int start, int mid, int end) {0 o6 A! |- f% ?# ?
int[] temp = new int[end - start + 1];
/ i' R+ b5 ^* {+ j6 [! Z& ~! l. ~ int p1 = start;& z4 c9 I& l0 h
int p2 = mid + 1;, F! o5 \8 f4 L! |
int p = 0;/ t/ S9 f6 @9 U4 n" a; b
while (p1 <= mid && p2 <= end) {1 A( U6 M1 l% f3 N' v* G
if (arr[p1] > arr[p2]) {' y/ B$ |+ V' {. a
temp[p++] = arr[p2++];8 w% t1 M' e( w g) o3 q7 N
} else {
3 }) G$ J5 C! _7 P) `4 B! R temp[p++] = arr[p1++];1 ^' x: ]& l, }
}5 I4 u8 a2 _' F6 U9 o. B( \; z$ U
}" ^. y1 C8 v: `5 U) ]
while (p1 <= mid) {
& J# l/ B) N- O0 L+ x0 { temp[p++] = arr[p1++];
s6 B: M/ r, l7 X }
* C+ T E4 r8 c: ]7 D while (p2 <= end) {
1 F; v( z$ h W2 {8 E temp[p++] = arr[p2++];
: J0 Z' Z9 k! \2 T. d2 f% f% Y$ | }
2 ?! T: H8 i3 q4 \5 M# g for (int i = 0; i < temp.length; i++) {- w& n$ W4 G1 S, N6 C3 M
arr[i + start] = temp;
8 \. E1 u+ e; v8 x3 I4 l5 O }
- s* Y' z& z, f5 b }
% S- ^+ L9 E) K( d# G* S( P# w/ S/ Z3 e/ R- |1 n$ S2 b2 _
public static void main(String[] args) {' f8 I7 d* p! X: v2 G6 h( A3 s" J
int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};7 ~" g- x& }! }5 M( T8 ^8 @9 w$ o& ?
MergeSort(a, 0, a.length - 1);4 Z& C' @( t0 O% p: x/ k
System.out.println(Arrays.toString(a));9 g; ?2 b7 T- R- k9 t& f! R
}) ]$ m7 n3 i0 H# ^- F" `
}
. {, ^. O, Z" I' h! m+ }. D, e: b+ \
) B: X, [4 b$ ]" E* Y运行截图
; b. v( }# P4 \: n8 f
3 W G; ?" Y, P5 b( l* G
: k! H) M$ c6 l( I$ d; U) u+ p4 G0 i8 O' Q
1、以上就是今天分享的归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)# G# q$ u& W. P! w
2、归并排序的额外空间复杂度可以做到O(1),但是非常难,不需要掌握,有一篇论文”归并排序内部缓存法”可以做到
: y4 d3 C4 F8 w' h) l& K3 f* _# g。 H/ P; E) U( L1 h
原文链接:https://blog.csdn.net/weixin_37686415/article/details/105180035
& O, B* q |. I% Y6 H/ r
( o# I4 V0 f# F8 R5 f/ `
- M# D4 v9 d1 s2 c: E7 | |
zan
|