数学建模社区-数学中国

标题: 神级基础排序——归并排序 [打印本页]

作者: 杨利霞    时间: 2020-3-30 17:02
标题: 神级基础排序——归并排序
2 G- s4 g' e6 c9 H' }+ j
& E' `" a0 A& f" p( ^  N
神级基础排序——归并排序
% h$ d0 l6 L- L" p
( ]% I6 [: E! L归并排序的介绍
& X. C* A. `! ]- {$ k$ [% s! o
" A! Z- M% [$ t4 `# J  m归并排序(英语:Merge sort,或Mergesort),是创建在归并操作上的一种有效的排序算法,其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
+ R" l: c  H5 a# v概念9 O: {5 W: ?% E. G
1 Q0 R/ ~! V0 ?% g0 B1 e
是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。# q. Z2 D% c9 c) [& B2 l+ \! ?; n
核心思想- F- n! p; N% V2 k' a, p9 M. O' \" ?
& h5 `5 j/ b+ o! ^& b
将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。
% ?- M  H/ q  W0 w% e% t( k* `* [9 Z5 n. S7 J4 S5 @4 Q# E1 C

- I- q9 \/ @1 o实现代码
/ ?0 i! q& v7 w, i: N* |  X. {" }import java.util.Arrays;
& Y$ Y$ ^8 R9 b, U. I' T6 [) q: V' K
0 j1 L6 M  @) H& Q% B7 Y0 m9 j5 z/**+ L7 y' y3 A; P, [" H
* @Author god-jiang
4 q3 f" E. D; c& j/ }, V5 j * @date 2020/1/13% V2 G3 @2 K* {( q9 D/ Q" O
*/! i7 O7 z, Y6 ]0 Q" |# _, v2 g/ l
//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
6 s# o! {9 V7 p( f' u. cpublic class MergeSort {9 Z1 D6 w; o1 {' v2 X! S: [1 H
    public static void MergeSort(int[] arr, int start, int end) {
. C; g& q6 J) F        //分治的结束条件
2 G/ Q' O) w, `        if (start >= end) {
0 P& y0 d* T4 ^. q1 Q0 n            return;) r1 F8 ^' p8 l2 L& f
        }5 T/ R# ]. E' T4 r7 O
        //保证不溢出取start和end的中位数$ b9 t# k: ^: _5 Z% `% O5 @
        int mid = start + ((end - start) >> 1);
  J+ |& q; A3 ?) R        //递归排序并且合并
1 U+ d% [) v% S. m        MergeSort(arr, start, mid);
/ H! r4 R& p+ Q2 h3 ?) }        MergeSort(arr, mid + 1, end);% }+ c3 S3 `/ X
        Merge(arr, start, mid, end);- f3 Y$ Y% e! t9 p/ t( U: o7 {% @
    }
7 `+ \4 r4 l# N* u" h, ^2 [( E0 V' O! t8 A) x! g  k
    //合并4 ]* ?3 H$ k5 `9 |7 M/ V7 [
    public static void Merge(int[] arr, int start, int mid, int end) {7 N3 o! W# T! m& j# Q0 O1 Q; ^
        int[] temp = new int[end - start + 1];# G- y9 W: F* n* E! g
        int p1 = start;5 S: W" F) x- C4 Z' ^: U1 b
        int p2 = mid + 1;
# R3 M2 s2 z) M2 W. M9 m5 q        int p = 0;
4 X& @" g! K; h& D6 k4 I9 u        while (p1 <= mid && p2 <= end) {
0 @# X/ F; J* m: l7 L, z+ f: T            if (arr[p1] > arr[p2]) {; D( ?* M1 W' i0 n5 ~8 d$ D( i
                temp[p++] = arr[p2++];
: c; l4 k& L  @$ T            } else {
, d3 I$ M, N% ^* J                temp[p++] = arr[p1++];; l* A: g9 k! C' L& p
            }
7 W8 Z( A% F- U) h* e9 C        }7 a" Z' X1 m( r, q) V2 A
        while (p1 <= mid) {
4 }! T. i8 h+ j& i1 A$ b            temp[p++] = arr[p1++];# O) {* U% h8 ^# m) P# K5 {, e. }/ I
        }1 L+ S9 Q* r$ j& _  G& [) g9 F
        while (p2 <= end) {
9 N9 l  W3 A9 Z* X% F            temp[p++] = arr[p2++];
1 [$ u5 Z$ y0 V  Y        }
, H4 `4 K1 G5 R. z5 D        for (int i = 0; i < temp.length; i++) {- K& P, D8 f" {4 T2 d8 h; k
            arr[i + start] = temp;
) t1 I  c$ j. H: {        }" C6 c: T, t7 w6 ]0 y% @; D8 b& |
    }: J/ C& w* i# @& r: A4 m! \# `
9 f5 F  u/ ^, }1 R
    public static void main(String[] args) {
- c' l2 O- }+ C- u        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
/ u2 N' H1 s* H7 O) @0 Q2 h5 ~        MergeSort(a, 0, a.length - 1);
* {" ~% W. {7 k/ g- V0 Q: c7 j        System.out.println(Arrays.toString(a));0 P9 S0 h: {  E' k! s6 j0 s
    }' \7 t" B& H5 q9 p
}
+ H3 G, M8 y, z5 K" [, K- _9 a5 K9 p+ w
7 r1 b8 ^$ |0 ]" |* |
, G- [! I. F3 N, ~2 I9 N  K2 M运行截图
( E  m% [8 t1 u' I6 T( E' L5 X0 v" e# z* P
1.png ( a+ o2 K5 Q5 |! I: j

- J: I5 r4 l; S8 g; B4 ]$ n' \1、以上就是今天分享的归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
3 X, {" y" R. i7 [& N( P; e( Y2、归并排序的额外空间复杂度可以做到O(1),但是非常难,不需要掌握,有一篇论文”归并排序内部缓存法”可以做到
" T6 T, ^5 e1 x4 }" e- e$ r+ t, [) @" V
原文链接:https://blog.csdn.net/weixin_37686415/article/details/1051800359 d3 R1 T" K. w7 v0 p/ K6 r6 c' S
2 \4 o! N/ y. P# @9 {) \

0 Y$ W' Z2 H' y, q




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5