- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 563412 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174246
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
" A( s' t4 [* ]1 A9 y* y4 {
8 q, z( X9 ?+ i! s4 V神级基础排序——归并排序
7 n% _; U- A% K
4 S, D# r; Y# r' A; Y$ q! Y8 U归并排序的介绍
* c( ?$ Q9 W' T) L9 F7 a5 N! L" `$ ]+ E+ o# y5 E ]
归并排序(英语:Merge sort,或Mergesort),是创建在归并操作上的一种有效的排序算法,其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。* K' ?* z D9 ~1 N/ u+ P- O& V
概念
' e) J6 J- u2 a8 r0 q% E; v/ l. f5 b5 ?
是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
( L9 H, E5 D" K x- x0 d: z: ^; {9 x核心思想
; b0 V: ~9 O5 S( z! i! j% ]
4 N1 i) j K4 F+ m y t将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。3 L, V# y# ]6 z& N0 i, S
/ ?$ t2 ~2 F6 o/ |4 g# D) n* I
4 i0 j* ~6 V# U7 E) p
实现代码
# ^8 F. B) t |6 W- r9 ]7 Fimport java.util.Arrays;* w g, |2 l1 E
4 h, d6 |% G# f3 b n. q$ U
/**2 A( P2 p4 I2 i: p! i$ t
* @Author god-jiang2 e0 Q+ b6 V, x9 A3 E
* @date 2020/1/13
! y4 L8 R& N/ X4 i4 w, t */
+ {8 u7 N; Z% `7 z//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)8 v' |0 W* @0 z$ i6 |
public class MergeSort {+ e' k# r6 ?2 Z" m1 r8 z
public static void MergeSort(int[] arr, int start, int end) {
6 G( K7 s' I+ u$ s2 c# v" I" G //分治的结束条件
( e2 D) t* q F8 m! S if (start >= end) {
" [* D1 t* k/ m( T1 @" s return;
2 F$ }; [' C3 K0 I2 U. g }7 F' a( V7 Q/ s' i
//保证不溢出取start和end的中位数
* F4 \! _% u. d5 U7 d% q* n" ~% O int mid = start + ((end - start) >> 1);# o5 X) l3 z# ?, A* l4 ~, ]
//递归排序并且合并
" f+ p/ z$ k5 I; {! s9 R MergeSort(arr, start, mid);
: }& k: C% y* v1 s' b5 E$ J6 Z MergeSort(arr, mid + 1, end);) V1 p( f8 ]3 Y' @
Merge(arr, start, mid, end);
/ c! Z( a9 l) y! O }
3 _1 z' x# T [+ s* Z8 L
9 r' G2 Z8 N, k9 H R4 X7 f //合并
( y$ y0 Q1 t4 Q3 c# p4 Z: b# O public static void Merge(int[] arr, int start, int mid, int end) {- M ^5 ]% q$ n8 y) x
int[] temp = new int[end - start + 1];9 d1 \ b1 d% a4 q: o
int p1 = start;1 `- t: q8 V/ }7 X" J) m' B
int p2 = mid + 1;1 \, q/ Z( j- }9 L, s K7 t* Y
int p = 0;
8 W4 G5 U2 m! b8 \8 @ while (p1 <= mid && p2 <= end) {- m( Z% ?4 n) D) T) ?! }
if (arr[p1] > arr[p2]) {* U8 f; N L9 w/ u
temp[p++] = arr[p2++];
6 e/ T7 c" Z$ B8 `, j } else { F& H4 K: Q+ r: x$ a8 p+ c% d
temp[p++] = arr[p1++];# R9 A w4 N7 s
}
5 q3 ~: T% w f( D4 [ z }4 Q# q& ~# c$ m4 ?' j
while (p1 <= mid) {% L3 R1 ]. O3 Q; p* s+ x1 k
temp[p++] = arr[p1++];
2 l8 U: C: u/ f! e/ p) d }$ X4 L4 W" [, L1 |" T
while (p2 <= end) {
8 O: e x3 S' N" s7 E temp[p++] = arr[p2++];* }4 b# k. k+ h5 W4 T% Y% F" K
}9 v6 T5 y- H! i0 ~0 p) f0 S. H1 M/ z
for (int i = 0; i < temp.length; i++) {
/ \: c8 a* b/ N. N3 S1 _ arr[i + start] = temp;0 I7 |" y% T" U: A( v, Y8 }' h& O
}7 E4 K3 V% R7 f G
}+ Q( n" b3 a( [/ d5 V5 M! d# m. E3 W
+ ^' Y3 E% m" y public static void main(String[] args) {+ }: G9 l, k3 t0 v3 g' v) z! V
int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};5 _8 v0 P3 |. }) o$ n
MergeSort(a, 0, a.length - 1);
' J/ b( b1 e4 O' t" o# L3 P* { System.out.println(Arrays.toString(a));* W1 N8 V! H$ i; w$ ]( I
}2 O, o* m/ ~ n1 I5 x: W
}! _ j4 x/ ~$ s' ]$ e
2 r& e8 T L# n; v
+ X( G% Z' C, N; _& Z+ v; b运行截图# ]1 s% H ]. S, z& R
! Y6 n% U# f3 C
/ w$ V( B7 U& Y1 X
" O, B- H$ T j/ u
1、以上就是今天分享的归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
2 V. S5 X) v- h% m" b2、归并排序的额外空间复杂度可以做到O(1),但是非常难,不需要掌握,有一篇论文”归并排序内部缓存法”可以做到3 y1 y. \' \# a, h/ a$ h
。
" c" }, k) `5 D, L6 ?; r9 q2 K, t$ C原文链接:https://blog.csdn.net/weixin_37686415/article/details/105180035% E: x! ^: |* e5 \: c7 U. q& ]
; F$ c# K/ N7 i; m: e+ p. e, V2 k& H3 q
% a% ]: N3 C( C9 U) E4 r8 n9 S |
zan
|