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

杨利霞

神级基础排序——归并排序
& v1 f5 ~# F- [8 K/ J$ M
归并排序的介绍

  F; A1 L/ b9 d3 o归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念
( X0 K3 M& G6 e( [/ Q
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想

将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


实现代码
( y, F' v, w! }3 X- F; Vimport java.util.Arrays;
$ l$ ?* V9 }7 E0 o5 P: J
: o% Z2 q! s8 m" g" O' B  {/**
5 Y% l* @# u" l. A * @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
( p) ~" d, g/ T9 S, ~6 Epublic class MergeSort {
" }# o7 |) J' q1 H0 i8 l9 Z    public static void MergeSort(int[] arr, int start, int end) {
0 ?3 }! F" Q# p' O- \! ?        //分治的结束条件
) n5 i) Z! U3 A        if (start >= end) {
            return;
3 D! A# Z0 ^+ s( e0 r* w        }
: t4 j5 p. w: v  W        //保证不溢出取start和end的中位数
& x* E" G$ [8 ?7 F; d6 w        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
) h3 k- v: n8 ~  k: a- L( E        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
( F+ {0 \; P  z# `        int[] temp = new int[end - start + 1];
6 L. }, {5 I/ E6 T% ?: k& m        int p1 = start;
        int p2 = mid + 1;
! d5 C5 O5 ]* }3 F! v1 p; D        int p = 0;
4 k! J) Q0 ^7 w" ]1 n1 b. i        while (p1 <= mid && p2 <= end) {
  K5 f+ x: X) E) @            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
7 F" q3 k, B2 U1 f( |1 y; `2 P            }
        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
/ W0 z  E0 z7 X0 [! p$ B        while (p2 <= end) {
            temp[p++] = arr[p2++];
& W/ |: N& I' e/ q        }
. Y' r8 c8 D3 w# Z. n5 H0 H+ R        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
$ A8 `6 [. H" e) Y: ^5 z7 W        }
$ r  n$ W, ~3 g8 h- c6 }    }

! w$ `" k/ G; z% {. c  X( T3 U9 t6 {    public static void main(String[] args) {
9 H; b1 u, c0 D1 G/ Z        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
4 p& w  Z8 n( I5 p% x+ _        MergeSort(a, 0, a.length - 1);
* |' n* x9 I, c& Y7 L8 @5 \7 c" @        System.out.println(Arrays.toString(a));
    }
}
* ~0 e( s/ J- D' b" n5 P( [: Y
( S9 z  a  }* B; _. z
运行截图
' C0 W1 M2 H# y+ R, `2 x

# A3 i+ n8 e* G, k% i
: ~! W0 k" ^2 b3 H- `" N1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
0 |* J# K* `. |: `1 ^) V. u2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
7 m. \! b2 S  h8 n7 S) X8 N8 K& H原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

; L( g; \& ]6 `6 x# F; l$ s* l