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

杨利霞

/ z; R0 H9 ]0 b0 j, B, @7 e
) q* E+ [0 D9 `* a- h- S神级基础排序——归并排序
0 L5 D& {7 K9 {8 ~! i
: X2 i, W8 V$ d0 o2 b" M3 Z归并排序的介绍
( J6 I) e+ k' x5 a' r
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
+ ]6 o) n4 b" E3 @" |概念
; k2 E6 p, f' O( w
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
7 _) K( l7 V0 }' H2 P2 N核心思想
0 _, y% ~9 F$ M# o- b1 f0 r
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
9 @+ @! h! I0 o* g) M$ W+ K
7 h1 D, I; f* X9 ~
实现代码
' v% H  J: N  f8 _2 W2 j- jimport java.util.Arrays;

/**
* @Author god-jiang
) M% d1 F7 W  V! c! h' a * @date 2020/1/13
*/
3 W6 p; W/ k7 g0 x% S2 M$ I//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
9 p5 y, i9 V  Z+ z& }3 p        //分治的结束条件
! s  y" r" x& d5 C- P        if (start >= end) {
) \6 {; b) ?  G/ r/ J. l7 a            return;
" A9 ^: v' D' `4 {6 Z- c8 h8 z        }
5 Z2 x1 `7 F* `3 \        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
$ f( s( S/ B; E        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
, n) a& m8 r; G2 P        Merge(arr, start, mid, end);
    }
* z* W" r: u+ W
    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
) {6 M8 ^( _0 Y7 {9 R        int p1 = start;
9 l- t: i. ~, P( f/ t  M        int p2 = mid + 1;
$ x2 x% k$ q6 t2 r% F! y        int p = 0;
' P$ g. e4 P4 i2 S3 j# K$ k0 q        while (p1 <= mid && p2 <= end) {
/ J+ p1 J7 q# I. ?" _3 m            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
' d  n' \9 p# V( {            }
        }
5 j  ?% u6 Y, G        while (p1 <= mid) {
6 K# `! b/ A. S$ F            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
7 y5 _* T% H; p/ X/ ~            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
        }
    }
% ]' z5 H* n# f. I) u) a& b
. Q% @% l( T; Y' g) [* m, ^5 p    public static void main(String[] args) {
6 N$ d- n8 ~4 C' g        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

5 T& Q6 S- ^" R& F( l7 L: n
运行截图

/ y+ Z  ^2 Y+ j% K3 e0 n7 S% m/ \
, {  e- K; B6 I( f
$ f& @2 N* J/ o: a- ~' N1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
  M5 d+ M; \" d6 W. A  L。
2 W0 j) j. P5 B  S( J原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

2 [# ^# N2 _8 x1 u  ~( r0 [