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

杨利霞

/ [: `/ a5 c- j5 M* ^8 ~神级基础排序——归并排序

8 A* s/ A) Q5 ~/ G归并排序的介绍
$ N1 Z' V( Z( _& a. r( M* l
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
9 E- D% c, h! M0 v! m9 [概念
8 S' P' b: A0 W& w0 X* h8 `2 j
5 Y: {3 e( O7 s是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
; n1 A2 }6 c" N7 c* F
4 y" o5 w7 }, \1 x( k% T将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
' S/ R1 [0 y# a2 n. F' F) N

. P) K' b5 A7 U+ V实现代码
6 q0 o# S0 ?3 j+ p3 kimport java.util.Arrays;
, o' m  ?* w& R8 X
/ h( o9 F/ @1 W  Y5 t) j8 `/**
* \5 T$ F9 W) Q! g+ `* r * @Author god-jiang
& t1 T- e/ L2 N * @date 2020/1/13
0 F+ b5 C( l, [4 g) w */
7 g. j- U4 S+ D8 o5 u1 v" U//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
, Q' y, i: a; W& U2 Epublic class MergeSort {
( n# O  X6 m) b/ \# D* t    public static void MergeSort(int[] arr, int start, int end) {
$ r" p# y; z4 w7 K+ h, `" r        //分治的结束条件
; C7 E7 l+ ]+ @8 J& {$ ^6 H        if (start >= end) {
, q1 I) P2 J6 p# F. |/ `) R$ `            return;
. o5 ^# v8 L# g2 ~6 B+ o" m        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
5 M$ [2 v5 _) M. B        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
3 |. p, A% [0 m, b: A7 ^! b/ e* W- l        Merge(arr, start, mid, end);
3 m! N/ k# u( R; ^( ~2 h  D/ C    }
+ ]+ R4 Y. D8 m9 z: O: H' W
' h$ \( t1 ]- b0 w8 \    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
6 a9 d/ N% V( @/ s$ c        int p1 = start;
        int p2 = mid + 1;
- t" H, Z: M8 W# A        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
5 x# A/ {' X& ]& z' p            } else {
7 I: R" U) H( O" N                temp[p++] = arr[p1++];
            }
( }5 R) e0 D) `5 {5 r5 A" k        }
: z" D2 @) z1 w# L, h& ?        while (p1 <= mid) {
# r9 K4 k- v8 g" L9 e* {2 B            temp[p++] = arr[p1++];
- u  H8 Z+ ^% w: X+ N0 F        }
, t3 S, ^5 L2 |# H) k' A        while (p2 <= end) {
4 w0 X! e9 ]" t* \  g+ d  \# T            temp[p++] = arr[p2++];
        }
) o' W- N1 t/ Y* d2 d7 U* |; ^        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
# E) s' L+ w- ^& E' N1 m5 X0 K        }
# e8 n' h. }, e! I2 q) E; G& ~    }
8 N) o  h4 y6 r5 g0 i. P
    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
/ g8 W+ U$ G) P) Y}

4 U& y$ m# G! k
- `) c9 M& e3 Q运行截图
7 O: ]8 P6 H7 P: i% S
7 [7 p2 O5 E& p" g" w  X0 D

8 _% {9 m5 f" e, d* W1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
- U1 c* Q( y5 G" D, Z2 ^2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
& G2 Y8 f, o" z9 Y) P$ Y& j原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

8 x" L! i$ o  s$ F
  C5 ]9 @: b7 Y