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

杨利霞

0 H% d9 O! u3 T2 g1 y
神级基础排序——归并排序

4 G5 b( R; ^+ ~& h$ K/ x1 p归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
+ t! T% N; e, N4 m$ Z概念

是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
* D& q. c  c; }- I4 e7 l) g核心思想
$ h1 n. ]9 a/ K( f- d
0 ~7 F. i( n/ v9 d将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

: 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
/**
2 n. S; p' [7 [! Z * @Author god-jiang
* @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) {
        //分治的结束条件
4 r* @1 _" V9 o0 t+ i& c        if (start >= end) {
3 O) _' `6 E9 o            return;
* a2 T1 w" d6 ]        }
        //保证不溢出取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 ]/ \    }

    //合并
    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;
        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 {
                temp[p++] = arr[p1++];
            }
        }
0 {; `+ B7 x0 p( H0 e        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
: t( J  q8 D. i, n6 Y- J: K        while (p2 <= end) {
            temp[p++] = arr[p2++];
, T! N/ l# E2 x        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
        }
    }
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};
        MergeSort(a, 0, a.length - 1);
        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, |+ D

运行截图
6 G% `& c0 U* }1 X9 I2 U
: `/ W/ z  E5 R  j) C

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