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

杨利霞

6 T- x6 v6 T( t" q) _# K8 O) C6 R, d$ w神级基础排序——归并排序

, N4 i8 g) k, t: k$ x6 V' M归并排序的介绍

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

6 z6 j8 [7 E2 N4 t$ e, b! k是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想

& \; ?1 S- e: t7 M2 A4 g$ e将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
9 z: y: c2 R) o3 l7 _# a2 _5 U8 G& y

实现代码
. {4 b! M* H5 L# E+ Nimport java.util.Arrays;
# ?( G( l: [" J% \* ]
/**
) c8 `) g4 ^% H+ j& P3 {5 l * @Author god-jiang
* @date 2020/1/13
+ c! o" T+ x' I */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
        }
  j) ?2 A3 B8 }- y2 y+ t        //保证不溢出取start和end的中位数
( F6 N1 X# ?1 L+ M! Q        int mid = start + ((end - start) >> 1);
# L8 f) B! }0 [% c        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

8 p+ x- Q1 R  [    //合并
& P5 \! ?* P) Q    public static void Merge(int[] arr, int start, int mid, int end) {
- V1 L% F: {! n' X0 b3 p, R        int[] temp = new int[end - start + 1];
        int p1 = start;
, a& E& I6 v" L% W# g" H- W5 c        int p2 = mid + 1;
        int p = 0;
  X4 Z. Q2 {7 ^$ ?' U( U* p        while (p1 <= mid && p2 <= end) {
9 x. s' @; V9 V$ m            if (arr[p1] > arr[p2]) {
+ S, I# y; V: v4 G9 w. u. K. t                temp[p++] = arr[p2++];
            } else {
+ Z+ `& c$ y7 y. v                temp[p++] = arr[p1++];
% @* I0 Z2 [3 i; _" g& ?            }
5 c2 E9 r! ?) g0 K; Y" X& V) D, K' x        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
# X& U* c4 T; W4 B        }
        while (p2 <= end) {
' n4 ^1 \* i( N            temp[p++] = arr[p2++];
- R/ `, A) Q3 Q3 D9 S8 B! D        }
, @3 m) X, n7 {/ g3 U) _1 M# c1 S        for (int i = 0; i < temp.length; i++) {
- E4 }' a& a% H6 d            arr[i + start] = temp;
# E* M! A  c+ n* L4 `! ?        }
    }

    public static void main(String[] args) {
9 u3 i  d2 P+ @8 V: P        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
, h5 U! Q( \, F8 i( E) `  Z        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
5 o6 Y3 N  }' L% @8 ^- X
( }5 g4 H! M4 [, p9 N! U( J
运行截图



& Y6 ~9 J  [, ^% J1 o0 q% }3 S1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035


+ v5 z5 ~- \; H, ]" _5 n; _, {