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

杨利霞

: N/ X+ S0 b. d3 U# p
神级基础排序——归并排序
" M( ~' z+ L+ i; G# L
归并排序的介绍
2 F' r; T' |. y% {. _% z3 q
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
/ A1 D, s7 B7 o; j概念

是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
1 Y, j+ U  X# _. @, p5 p核心思想
( }0 |6 N. b3 w& D
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
& R( f" `* D6 |
+ s+ F) _" W  H
, `* Y5 z% g2 \' h. g" K/ y+ c实现代码
$ o: X; s! Y$ l: simport java.util.Arrays;
  ^8 x: d' D9 A: u' b
% M$ w/ Y5 v: }, a/**
* @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
. A- H& k  C+ Z" u2 s    public static void MergeSort(int[] arr, int start, int end) {
; I( d6 R% F$ ^4 \  x+ R7 g3 a7 B        //分治的结束条件
        if (start >= end) {
            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
- V( q/ X5 Y; E: e; A% X. C        //递归排序并且合并
( E2 J7 Z& a' Z) G+ Y2 s+ O4 A0 b. w$ U        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
+ W/ @* Q) S2 P) Q. K    }
0 K9 I* H7 X4 I: S
1 t0 L2 }5 \0 L: D9 [6 @  W    //合并
6 A$ y% ^! [( r5 w1 G. @: I6 ^    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
' L' R! z. A0 J+ b/ `# y) I# ^: w        int p2 = mid + 1;
! s8 X6 _+ X7 {2 X        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
  m1 x% \6 C7 B- I. A6 p7 }& u$ M                temp[p++] = arr[p2++];
: {! \: G" r5 ~$ a* t            } else {
; z" g0 v: _4 L                temp[p++] = arr[p1++];
& r, j& \) W6 l' ?6 i: {* t# c            }
        }
" E5 a; L' G; R        while (p1 <= mid) {
( m" ^4 V& R3 H& \            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
2 p7 b5 ^  g5 ?3 ?. y  W        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
9 |/ L1 g1 p/ d* F8 S. E5 I# W( A% [        }
8 J% P0 Q: `$ ?" D; O2 m. n  [5 d: `    }

3 _  L+ }, o7 c    public static void main(String[] args) {
1 q* Q- {5 k7 m        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
% |; C+ Y; m* f& n" _}
  g6 o( O9 x4 Z2 ?* U) J& o
) G0 z. _: M; b
运行截图
2 B5 ~1 Q+ d, }
' {* k0 E6 F' J, C4 `* N0 E. s( b

1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
7 d  c, w% J: A) C! ]