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

杨利霞

8 q, z( X9 ?+ i! s4 V神级基础排序——归并排序
7 n% _; U- A% K
4 S, D# r; Y# r' A; Y$ q! Y8 U归并排序的介绍
* c( ?$ Q9 W' T) L9 F7 a5 N! L" `
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念
' e) J6 J- u2 a8 r0 q% E
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
( L9 H, E5 D" K  x- x0 d: z: ^; {9 x核心思想
; b0 V: ~9 O5 S( z! i! j% ]
4 N1 i) j  K4 F+ m  y  t将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


实现代码
# ^8 F. B) t  |6 W- r9 ]7 Fimport java.util.Arrays;

/**
* @Author god-jiang
* @date 2020/1/13
! y4 L8 R& N/ X4 i4 w, t */
+ {8 u7 N; Z% `7 z//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
6 G( K7 s' I+ u$ s2 c# v" I" G        //分治的结束条件
( e2 D) t* q  F8 m! S        if (start >= end) {
" [* D1 t* k/ m( T1 @" s            return;
2 F$ }; [' C3 K0 I2 U. g        }
        //保证不溢出取start和end的中位数
* F4 \! _% u. d5 U7 d% q* n" ~% O        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
" f+ p/ z$ k5 I; {! s9 R        MergeSort(arr, start, mid);
: }& k: C% y* v1 s' b5 E$ J6 Z        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
/ c! Z( a9 l) y! O    }
3 _1 z' x# T  [+ s* Z8 L
9 r' G2 Z8 N, k9 H  R4 X7 f    //合并
( y$ y0 Q1 t4 Q3 c# p4 Z: b# O    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
8 W4 G5 U2 m! b8 \8 @        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
6 e/ T7 c" Z$ B8 `, j            } else {
                temp[p++] = arr[p1++];
            }
5 q3 ~: T% w  f( D4 [  z        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
2 l8 U: C: u/ f! e/ p) d        }
        while (p2 <= end) {
8 O: e  x3 S' N" s7 E            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
/ \: c8 a* b/ N. N3 S1 _            arr[i + start] = temp;
        }
    }

+ ^' Y3 E% m" y    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
' J/ b( b1 e4 O' t" o# L3 P* {        System.out.println(Arrays.toString(a));
    }
}

2 r& e8 T  L# n; v
+ X( G% Z' C, N; _& Z+ v; b运行截图



1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2 V. S5 X) v- h% m" b2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
" c" }, k) `5 D, L6 ?; r9 q2 K, t$ C原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

; F$ c# K/ N7 i; m: e+ p. e, V2 k& H3 q
% a% ]: N3 C( C9 U) E4 r8 n9 S