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

杨利霞

神级基础排序——归并排序
4 j" y- c% F3 G$ i' S5 ~( ?8 O
# e8 J: B1 e2 Q! t+ k1 _; R归并排序的介绍
2 G) e2 S) B, v& L8 }) n3 z
1 ^/ n2 \$ n& v4 d& ~8 b归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念
/ n3 v+ D8 n' p# H
; Y( q0 ?7 w; o/ m是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
3 r( K. Q9 i0 u' s) `核心思想

将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
$ p- w5 U1 D8 p8 z

实现代码
import java.util.Arrays;
3 y6 a. C- O4 h7 N4 i6 `2 y2 t
/**
# J& l' A- r- Q' ^ * @Author god-jiang
* @date 2020/1/13
, a- c" E  Q: w, ^( n- ?3 r" x8 D */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
: R! \8 \/ [. hpublic class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
3 a0 x# I( e, E# T# S7 I  L        if (start >= end) {
" r- a  {! R5 Z' m  G; |) H            return;
        }
* h, G; `* t+ C2 C$ M        //保证不溢出取start和end的中位数
+ `9 l6 o' h1 n8 j+ E        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
' f: z: {! _, J5 Y* f9 t        Merge(arr, start, mid, end);
$ h! `0 |; a, P: H2 Y$ i    }
! w4 c# C2 o9 `; u; Y; Q
; z! ]9 T" s; l5 ?+ F. C# B    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
( I/ v( f+ v& F1 o" J' T0 f' L' |        int p1 = start;
        int p2 = mid + 1;
  V9 k# G6 [) E0 e: h7 Z        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
/ U  {1 v+ y# ?8 M4 A( G                temp[p++] = arr[p1++];
. M. d5 U) o& t  {# J, v$ W# E3 t' |            }
        }
, y% x+ K) w6 x9 h        while (p1 <= mid) {
4 y/ a: d$ k( c- X/ y            temp[p++] = arr[p1++];
        }
( d: u: H, e* l: d/ G; \        while (p2 <= end) {
$ t/ j6 o( `3 M+ o+ h            temp[p++] = arr[p2++];
        }
7 w- R& a$ _& |3 \( ^- f* m        for (int i = 0; i < temp.length; i++) {
! d* P% C' B# T5 a+ Y/ w/ Y' y            arr[i + start] = temp;
9 L& `1 e* r9 u7 z) E5 m! e) j3 |; c        }
    }
2 G' D% M9 F$ \8 S+ g+ |
    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
1 s5 g' o, ?; B6 x" c        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}


运行截图

* k! z3 ]/ X. F! O* P2 Z8 O; A
, Y7 ^3 M+ `' [' l5 R( c* P
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
; T1 n( v* o7 l* p
2 ~! v$ k& q7 R4 ~