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

杨利霞

/ s% S2 y2 F* h5 e神级基础排序——归并排序
1 v  T& i) h. b. n$ [
0 Z5 L( A# }3 p1 v0 y0 m3 j归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
/ V* Y. X# x( L: g( k概念
. u; W+ F+ y8 _$ |5 {" x
+ t6 {' M; w4 m2 O. O是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
- J0 @+ V* V3 Z- T( F0 V% i* s& _核心思想

2 m, M$ L: c  N: B: }8 @! ?" V将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
9 C$ [$ L+ Z' o0 P4 w; V1 j1 \" \

1 {0 U" Q; ?4 ]8 L* Q9 B实现代码
import java.util.Arrays;

/**
/ w6 l" R% T9 n8 q1 H2 C * @Author god-jiang
* @date 2020/1/13
*/
/ N7 T% \  x7 {1 A//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
# k% ?% R/ G2 d$ N" o6 C) Y% ^public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
        }
        //保证不溢出取start和end的中位数
/ B) i8 z' v8 o- {        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
7 I# D/ O, q7 d% a: i1 N        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

& v; p* I1 ~$ j+ Y% _& t    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
: E: X) Z2 f0 j        int[] temp = new int[end - start + 1];
        int p1 = start;
. x0 b* H( \& K5 `# c. i. h4 c& E0 \        int p2 = mid + 1;
" w) ^6 k. b, m        int p = 0;
5 i* s$ K# S) D& n" W7 N        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
1 H* W; p! \7 H+ t! ]3 Z                temp[p++] = arr[p2++];
            } else {
" N5 @6 {5 y3 p9 b0 ?0 {                temp[p++] = arr[p1++];
- C5 m- @( S3 d" l) w            }
        }
        while (p1 <= mid) {
+ L9 p  L8 C8 S* U( p            temp[p++] = arr[p1++];
1 ^( `6 ]# \- J8 O( t3 s        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
& {. ]8 J# w8 j  N2 e- s8 M            arr[i + start] = temp;
        }
  P2 P) _4 a1 ?7 w) q5 m) ^" @    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
7 }; V! Q2 [; w        MergeSort(a, 0, a.length - 1);
$ m/ _; p8 I$ G) w        System.out.println(Arrays.toString(a));
    }
}
% h: g. V/ I9 R- I
, D% l4 p! W3 _! ~! t
" E% I9 W, e$ c运行截图
- U" U. @* R7 F+ n3 k7 a
4 F1 \# j& _  X3 Q' ^4 q
' `" k9 F- m5 k8 Z/ B5 \6 B
# U( u" x! S' ?( ^- O  H1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
& k+ Q8 x+ k. Z" m1 p2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
- o7 j5 [2 t$ L: K- \5 R0 `$ Y