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

杨利霞

4 _# o. U: R' f
神级基础排序——归并排序
" [# n/ P8 q- P( `  i) ~
, Z% r- ?5 W- i" S! E归并排序的介绍
& f( D0 r  }. W* f
& p9 X# C" Y: I归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
) c! y2 }% U  m概念

是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
7 _( ]( n4 I! u1 G8 |8 l/ O
) Z5 B; T" [- m6 I- C* j1 H将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


实现代码
import java.util.Arrays;

; a: ^5 \' |6 y& a/**
* @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
& C5 P, |: X  R    public static void MergeSort(int[] arr, int start, int end) {
$ d0 s  O6 z2 h* Q  U  K" Z        //分治的结束条件
        if (start >= end) {
) O, }& m: [" B: k            return;
        }
2 T. s& R- D- ~        //保证不溢出取start和end的中位数
+ o) H% |) }* }/ E+ F  Y        int mid = start + ((end - start) >> 1);
$ O* r" ]& G: `: a# L; P0 P% S        //递归排序并且合并
        MergeSort(arr, start, mid);
3 {2 d5 g* g) i        MergeSort(arr, mid + 1, end);
$ c" u4 [8 M; a+ Q& H7 m$ S        Merge(arr, start, mid, end);
    }
$ Z( L* n6 q3 y0 M
    //合并
8 a- H8 B' E6 g. w+ O6 P    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
7 ~% L; c' H, g; f+ A6 i        int p1 = start;
* {2 R( e% A% p1 k, h6 [- `$ r        int p2 = mid + 1;
        int p = 0;
( g' U: g/ p3 O2 ^! Z0 E        while (p1 <= mid && p2 <= end) {
* l9 O3 m5 J7 q7 [$ C            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
; T; s* l7 e5 V8 \8 y2 D2 o: S2 H                temp[p++] = arr[p1++];
            }
+ A8 ~8 d! v( J! u9 t4 G# }0 f5 i- s        }
9 s4 j& L- t# Y        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
1 V9 g" N* ?; X        while (p2 <= end) {
            temp[p++] = arr[p2++];
, \, j* a3 P! Q, g& G        }
9 ]* e. f( H$ ^* C1 F5 [/ ~5 f        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
% P& ]" @1 c% g9 p        }
; O4 M; `. U! ?' t    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
8 y5 F- w- c( R+ l- b& d9 U4 p        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
4 U/ B; P  B. @}
' f" l' q6 G3 H- t5 w9 ~& k

运行截图

: W4 f# Y# D' c" c+ E

9 u; A7 M* h5 C9 J- H& _7 r: x, [1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
) T1 p6 V; a$ T# n2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
- s" P1 x4 {; v- A/ |原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

- j3 K7 M) I% {! I* R- J8 t% W
* j& h5 N6 g4 B0 p