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

杨利霞

. F' [5 m8 [, @2 m8 H
; l  Q4 I6 x7 Z: {7 Y神级基础排序——归并排序

归并排序的介绍

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

* S% M/ H, f: A是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
* {/ ~3 G$ m0 @# u& E1 ]核心思想

/ j- K, J8 w( O4 w将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

/ }$ V7 Y  `: E# K0 P% v
7 G3 C  g9 v( _" e" S实现代码
import java.util.Arrays;

8 C0 s1 u  a8 m1 X) p/**
* @Author god-jiang
* @date 2020/1/13
, R0 c) A7 m4 m% [8 _' c */
( n* g5 w6 S/ I1 I//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
, x+ ?% \1 r7 U. j! fpublic class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
& k9 V% i3 d5 U        if (start >= end) {
% e; }0 C% v/ I0 b# ~" }; P            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
: m6 W8 ~* G9 t, W        //递归排序并且合并
& z* H& z4 w% S. O6 |        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
3 i: P: c6 c  `0 w6 |0 @9 q! Q        Merge(arr, start, mid, end);
1 T( Z" `( e+ D) j0 n7 t    }
5 r6 ~2 ]8 n3 N( t* d& h% M
    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
% X- Q6 l9 Q5 h+ S# x        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
. Q% P2 k* M7 B            } else {
                temp[p++] = arr[p1++];
            }
, b' \  _& |/ s5 m+ P6 D. l( `        }
        while (p1 <= mid) {
- S4 T: \# r, {. D2 c1 f            temp[p++] = arr[p1++];
7 ?9 I) d- ~# i7 k        }
        while (p2 <= end) {
' l- h; A7 u7 A, y3 ]6 X5 T            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
7 P) i5 v  J" u  R3 w7 ~        }
    }
. ^1 d% Z: |# t4 t
    public static void main(String[] args) {
2 T7 i/ c6 p( n4 z        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
' ~  w) E! I4 ^- @5 f9 x5 ?        MergeSort(a, 0, a.length - 1);
0 m) [# R7 V! W4 ?$ x        System.out.println(Arrays.toString(a));
    }
: N  S$ ]7 A& T}

4 T; j0 q$ V5 J, f$ M
运行截图
; ~% h0 e! X( s

3 h% P! q, H/ w/ k( t' J1 ]
* [2 t' O) d7 [5 V: s; e' Z/ t1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
$ E7 |' [: f$ i/ Y# R: V3 d% q。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

" ]2 i5 G$ {  M7 T