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

杨利霞

) E* C  J3 h% _) [9 x1 G  ?
神级基础排序——归并排序

- e9 T+ f6 Q$ F4 l% Z; w0 E; f归并排序的介绍

% ^% E; {% e/ ^; E6 {9 K/ Z2 o归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念
3 ?7 t1 L  V8 U* m' H9 e8 G
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
/ M6 q' e" }% C5 o
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
( X% x$ }* l6 h8 E5 E- w$ y' u$ W
. F" ?9 L/ c- r; p/ P
实现代码
import java.util.Arrays;

/**
* @Author god-jiang
* @date 2020/1/13
*/
- v: V. t4 I4 ~8 w6 {5 G; {. ?/ w9 h//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
3 Z6 m- i3 i9 a* h9 p. Ypublic class MergeSort {
1 _. x& y, u* D! g    public static void MergeSort(int[] arr, int start, int end) {
. B4 k4 D0 i" f  l8 x0 D+ _        //分治的结束条件
# d+ f# p+ t) |/ T9 D* P* b" D        if (start >= end) {
' x, o+ t5 I( L0 R            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
# r2 b% d2 g0 H. d& ~( Z9 h        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
. `0 E4 ^$ Z& G- C        Merge(arr, start, mid, end);
+ O3 Q) j; N* L7 x2 S2 s) T2 J4 M    }

. G) s4 u% ^0 p! b0 q- w: M- L    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
5 U1 M9 ]7 G( Y$ M1 G, g5 ~* Q. h9 B        int[] temp = new int[end - start + 1];
        int p1 = start;
( z9 J, a; j/ z+ |4 H7 r" q/ D        int p2 = mid + 1;
7 k/ D  q. g1 i% w        int p = 0;
        while (p1 <= mid && p2 <= end) {
$ p: C! E7 A+ `9 x( u5 ~, X+ L) T            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
8 o( s8 [) b9 H6 r4 e7 w# z            } else {
7 U, M7 C8 V8 D/ U+ k                temp[p++] = arr[p1++];
) s& B7 V3 q4 K5 `9 }+ ^* y3 ]            }
        }
' X* \5 k  b2 T$ F& B/ \        while (p1 <= mid) {
: f8 h9 u% N; l9 |; e! ?2 `3 u            temp[p++] = arr[p1++];
        }
8 _  A& C' k& l        while (p2 <= end) {
3 ]) r! r# Q2 Y  c            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
- y3 V  q! ^1 \) p6 V3 C9 S3 Z            arr[i + start] = temp;
        }
2 o7 w" K- Q' [8 `( U3 p/ d    }
' S5 ~! \9 |5 m4 D# Z8 O
    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
% \! w3 U5 m* s* c6 G
* s0 n0 }  j+ i9 f# b
: E0 H- z6 `6 z- d* P1 U! B; N  G运行截图
0 C' j9 r  h) I; J

3 d7 F* B! \" ^; o0 Z$ o0 G( U' Q
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
( b5 B8 `" y4 @+ Z原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

! q0 p0 Y% G1 l
) ?0 ]$ G, G) x( c8 C8 k8 q