QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1861|回复: 0
打印 上一主题 下一主题

神级基础排序——归并排序

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-3-30 17:02 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta

    0 H% d9 O! u3 T2 g1 y; n3 q2 o2 _# f9 l
    神级基础排序——归并排序" e# T) X1 l5 j. [3 Q

    4 G5 b( R; ^+ ~& h$ K/ x1 p归并排序的介绍$ n% f3 l2 y" ^- K! X6 `6 O$ G2 g7 S
    * g  o7 J: `+ ~7 Y
    归并排序(英语:Merge sort,或Mergesort),是创建在归并操作上的一种有效的排序算法,其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
    + t! T% N; e, N4 m$ Z概念& C! W/ p# o2 [/ C+ o
    # d8 U( }) t" j" [$ Y2 K
    是利用递归与分治的技术将数据序列划分为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
    * D& q. c  c; }- I4 e7 l) g核心思想
    $ h1 n. ]9 a/ K( f- d
    0 ~7 F. i( n/ v9 d将两个有序的数列合并成一个大的有序的序列。通过递归,层层合并,即为归并。! S7 B! u3 I3 C$ j% K- m/ N8 t! q! w+ H

    : R2 A8 Z0 F1 _3 [1 ^3 K* z
      N7 y. }3 B6 o实现代码
    $ O% h  g4 ^" N, X' Qimport java.util.Arrays;
    " Z7 D. `- u. |6 k& R( z, L: t! G6 j  Z3 i" r- F5 V
    /**
    2 n. S; p' [7 [! Z * @Author god-jiang9 }5 h: t3 |5 q, x
    * @date 2020/1/13
    ! s# s$ }) H" ? */
    6 H/ ], B2 H( |' v3 e/ `) b8 \//归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
    , U0 |7 _$ x" B$ |0 B. ?& [3 _$ epublic class MergeSort {
    : x" |, V% A+ l0 F! ~    public static void MergeSort(int[] arr, int start, int end) {* o. P: r! I5 ?, ?8 E5 c
            //分治的结束条件
    4 r* @1 _" V9 o0 t+ i& c        if (start >= end) {
    3 O) _' `6 E9 o            return;
    * a2 T1 w" d6 ]        }( w$ i& N9 i0 I
            //保证不溢出取start和end的中位数
    ( L. P' R) ?$ I  S        int mid = start + ((end - start) >> 1);
    ( ?# w4 L  v: A* S  E        //递归排序并且合并
    7 R7 Z+ H: n$ i- ^! O% J+ O7 d8 F        MergeSort(arr, start, mid);
    ; ^% d: E; k, V        MergeSort(arr, mid + 1, end);
    ! O. Z: [+ {( n9 x- h        Merge(arr, start, mid, end);
    ) f" P% P4 C4 o. ]& ~5 |0 ]5 ]/ \    }) X7 X0 [% [4 ]
    - _, z4 C- ~$ Q1 |# f
        //合并$ @9 e9 p' X1 B5 A" ^
        public static void Merge(int[] arr, int start, int mid, int end) {
    - S+ B5 W; O& U0 }" |1 o' `, f        int[] temp = new int[end - start + 1];
    $ s- \! F" z( j* Q2 X- u        int p1 = start;
    ( v  m$ s% W1 Z& A" r        int p2 = mid + 1;
    - R  V, z; l- m  Q5 G        int p = 0;, T" w7 \! v- o
            while (p1 <= mid && p2 <= end) {
    3 X9 I5 _7 `& H; l0 a            if (arr[p1] > arr[p2]) {
    # w% V+ o5 y$ r                temp[p++] = arr[p2++];
    0 [7 m7 d2 E+ p7 G( L' ~  a4 V            } else {" G1 W$ v% c8 ^. a
                    temp[p++] = arr[p1++];$ H  {. T( N  j2 L: C
                }0 c* Q% t9 \2 Y7 b
            }
    0 {; `+ B7 x0 p( H0 e        while (p1 <= mid) {% M$ d! p& X* E2 l8 Z
                temp[p++] = arr[p1++];& s: O) g, Y" m5 _
            }
    : t( J  q8 D. i, n6 Y- J: K        while (p2 <= end) {( p4 ?, q) e: ^( v: m4 n% m3 P
                temp[p++] = arr[p2++];
    , T! N/ l# E2 x        }$ B5 o5 g% v- i
            for (int i = 0; i < temp.length; i++) {. l$ ?( E, k/ `) D  b' k
                arr[i + start] = temp;6 f+ L, X* X, @. {; R, m
            }+ U$ ?: A2 ^; v7 G
        }
    4 `) r- g) o/ Z. Y6 s6 u. Z. ~
    : ^1 L; \4 N( x: P+ a( o* i" r    public static void main(String[] args) {
    5 o( M# R4 F/ X+ d" u2 D) R2 T: A        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};% X7 R2 \0 s& |$ i/ Q
            MergeSort(a, 0, a.length - 1);0 T6 k( D1 r$ ~& l. R; R$ [
            System.out.println(Arrays.toString(a));
    8 Y6 N% R9 Y) M" ]8 }    }
    4 n3 L/ T" N" E3 Q/ |% [+ Z. `% U}
    % Z* s& P* F0 W9 O, f8 z, |+ D4 Z1 d2 p. n) B/ q& T
    9 F9 t+ F, O% C7 j
    运行截图
    6 G% `& c0 U* }1 X9 I2 U
    : `/ W/ z  E5 R  j) C 1.png $ S# x/ \" y. t7 H, L, i! k
    / K2 w; o$ u& x' y3 S
    1、以上就是今天分享的归并排序,时间复杂度为O(N*logN),空间复杂度为O(N)
    5 T+ Y% R/ O* f9 J2 ?2、归并排序的额外空间复杂度可以做到O(1),但是非常难,不需要掌握,有一篇论文”归并排序内部缓存法”可以做到
    : G6 m) r! K  b! u8 \' A8 N
    # @' v+ m  B) d( I原文链接:https://blog.csdn.net/weixin_37686415/article/details/105180035
    7 U6 C, q9 c1 k( n
    - v1 D5 _% n& O! [3 w5 M" G- |( X; u% e% {; [  W% h
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-7-26 06:37 , Processed in 0.457305 second(s), 54 queries .

    回顶部