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

杨利霞

$ I9 X" d2 R+ _. w神级基础排序——归并排序
( d* N6 ]& T8 F' x6 _6 A1 s, ~, [
' O, k$ V, L" w2 y. R! w: p归并排序的介绍

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

& \$ G' X2 k5 r7 b7 k$ ~/ t是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
1 I! c' i! @, ^" f1 S
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


实现代码
import java.util.Arrays;

/**
* @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
( V8 w: [4 R8 Ypublic class MergeSort {
, Y% v! w9 ^- C3 r0 h    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
# V9 m. K, K, q: N3 E4 _7 E& g' X$ p        if (start >= end) {
            return;
        }
" f) L7 x) j7 H# R+ }        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
9 f- K- G# c7 \$ G! z5 o/ o0 u        //递归排序并且合并
        MergeSort(arr, start, mid);
, V0 q$ T- y  O; V( l# A" t2 A        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

9 H! m1 |2 d8 i4 A' L; o7 n; ]    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
1 M- H7 j0 e9 b( H* u* b( L        int p2 = mid + 1;
        int p = 0;
2 x9 a# O2 q( N+ ?        while (p1 <= mid && p2 <= end) {
+ \, a, @; |" y" G% Q            if (arr[p1] > arr[p2]) {
3 }( r7 g1 d: S" V" t2 m, V                temp[p++] = arr[p2++];
: @$ v# M0 f# C* Z; W% w: I            } else {
* a8 n2 {+ G$ X- h3 U                temp[p++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
! Y$ f* o5 |! h: i/ `( O' D            temp[p++] = arr[p1++];
        }
. K/ T' W+ N8 r        while (p2 <= end) {
/ o: {+ l; s' a            temp[p++] = arr[p2++];
5 j- U1 M+ {0 p, L% U# [        }
, s' x  n1 ]5 i- G        for (int i = 0; i < temp.length; i++) {
$ F; }1 v+ U, e! B- ~& K            arr[i + start] = temp;
        }
    }

( R0 R; P' G$ r% w/ N    public static void main(String[] args) {
; y1 t2 n+ ^: U0 p. V        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
6 e7 M0 G8 {5 r" d" G+ l9 J+ Y        MergeSort(a, 0, a.length - 1);
( a- o) T& X2 ]1 ]1 F# }* X) n7 t5 U        System.out.println(Arrays.toString(a));
    }
}
* Z8 m! u0 J5 _5 ?5 L

运行截图



/ [6 i  M$ A/ H# n! q5 Q; k3 C1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
5 c( o( S& A1 G& i: g/ Z7 r- i2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
- W4 ~& E6 j* }& U( m: {& {原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035