- 在线时间
- 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年大象老师国赛优 |
4 _8 B R) u4 b& @$ I& I0 i
0 q2 Z# ]% l7 K神级基础排序——归并排序
r4 w R3 p! e% B. p0 b; e! c( O- B( o
归并排序的介绍: s, j. G) }" m5 b
e' P/ {+ {: T2 i; j: T4 f6 K V
归并排序(英语:Merge sort,或Mergesort),是创建在归并操作上的一种有效的排序算法,其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
2 Y$ W m+ e# [0 ^+ s6 K概念
4 ?0 v. A0 H& e- O% O6 S
. \" M! D& S) @$ \ R( I: D是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
. x% N( S$ n! H. L+ e核心思想: u6 f3 b, j8 k/ s! U
" q# T4 i$ `% F: u( }
将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。8 {! X: g+ t- F
' _) B7 r( P: p
- N9 P$ B0 j3 O$ v# g4 @5 E
实现代码
8 @# G; ^, e7 |+ t/ |import java.util.Arrays;
3 F( |. Y% [( r# m( w
$ H1 g# E7 w& F" k/**
7 i6 ^) \* W- Y$ u5 R) d+ v * @Author god-jiang
# P( l0 e, J' W0 z+ T' i+ U' D * @date 2020/1/13% |8 V4 V) ~ ^2 v% V: j
*/
$ h Y1 c: R9 D `//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)6 Y) {; x. l! S1 G9 ~* v1 G) k) U
public class MergeSort {3 }4 d% i3 v/ q0 G$ b' n
public static void MergeSort(int[] arr, int start, int end) {% x; P: a$ R; a2 l* a0 g
//分治的结束条件9 R: g5 T' T9 f4 f' y5 d
if (start >= end) {$ w0 t/ H5 R0 Y2 n( t2 k }
return;
% W% K0 r5 [! @. O/ t6 ` }! D& G5 N% o' l8 P# {3 |
//保证不溢出取start和end的中位数' X2 F/ U2 Q$ ^8 ]; R9 O4 ^1 o
int mid = start + ((end - start) >> 1);
+ H+ @) }; w) j3 h. h //递归排序并且合并 Q8 C: H( a2 R+ S% B
MergeSort(arr, start, mid);
/ }2 m4 ~; h' i" ^ MergeSort(arr, mid + 1, end);# ~8 e m% T8 h
Merge(arr, start, mid, end);# N9 H7 x3 O9 r" x! R( I
}. s S1 V7 S6 v- d6 Z$ @0 ^6 n
& C: B+ h) t- H, E. E( c
//合并
g' h6 l6 ^/ c9 ^& V2 M& R public static void Merge(int[] arr, int start, int mid, int end) {2 j5 C2 ~" u& X( @
int[] temp = new int[end - start + 1];& L& P/ Q i! ?, Y3 H
int p1 = start;9 P, K9 |% D: y) b4 @% d6 V
int p2 = mid + 1;; O& j' j3 A4 M0 Q6 k5 i$ v7 {+ M2 K$ D; L
int p = 0;5 O' I5 R; j. }6 m/ r5 E# V* `
while (p1 <= mid && p2 <= end) {
! m: A( W+ k8 H; t) R e if (arr[p1] > arr[p2]) {5 |! }- {6 y( `) m2 G
temp[p++] = arr[p2++];* |! X V$ p1 @2 o
} else {
" g" G% b4 {; ?5 g+ g+ A) R- m1 f temp[p++] = arr[p1++];
* }% B% c% _8 z8 ]. C$ H }' ?+ T% ], z! Q. |! m
}
9 h- o1 D2 |* e% O! ^% I' \# [ while (p1 <= mid) {
1 Q( h$ b% w& m( E3 P# J temp[p++] = arr[p1++];* w& W- }0 q; o. K5 ^: K
}; Z% ]3 ~3 G5 F" F- T
while (p2 <= end) {) r- e' ~6 V6 ?+ w5 H: {
temp[p++] = arr[p2++];- T/ H9 Y' [4 W; K( X- o) F
}5 t4 L' b) l; m5 Y: S Y/ c$ q
for (int i = 0; i < temp.length; i++) {
; \7 o" O5 @- m arr[i + start] = temp;* s/ c+ O3 C E) E; J
}
' i( C( v" z, }, l& V* A# ~ }
: x: p+ _- ~$ i- A* e
, W0 V1 q+ d# Z/ X D/ f$ C7 X public static void main(String[] args) {
. k# h6 j T3 l& ?( R' ?- Q int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
6 E7 J! u; R, [3 l7 U, o MergeSort(a, 0, a.length - 1);
! y6 z8 F6 _! X System.out.println(Arrays.toString(a));& W/ _- s- J' ]
}
4 j% A. B' W8 c. [4 _( i! c}
. S! F0 D$ X- L3 y
" B3 z2 P6 v/ a( |' c2 [# L- f+ z4 c# P; {
运行截图
% I0 v/ Y, F! g' X! ^4 M6 z3 e6 L9 }& Z% r8 y, W
2 Z. K3 z- L" n+ g" C- S( Q5 v
8 }! B5 A1 P- k6 l) w3 l( w1、以上就是今天分享的归并排序,时间复杂度为O(N*logN),空间复杂度为O(N); z; K1 M) T4 c0 P( _; d4 C/ d$ [! {1 l
2、归并排序的额外空间复杂度可以做到O(1),但是非常难,不需要掌握,有一篇论文”归并排序内部缓存法”可以做到' G& x& U; A7 o6 P7 X
。
' W- K7 f; A. Y原文链接:https://blog.csdn.net/weixin_37686415/article/details/105180035) a8 C% A9 W5 H; J' J) A/ W
3 S o/ B5 _" k" J. W/ t/ `- |
5 y" ]: }" v @" z+ B
|
zan
|