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

杨利霞

1 r& }/ \. |% P0 _3 t+ O1 d
神级基础排序——归并排序

8 h- l: F2 m0 l6 i/ f; `( C: O2 S归并排序的介绍
  C4 @+ Q3 P1 c" O: J
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念

1 h. P% B! J/ L是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
2 I; v) @3 |4 H6 `4 z0 B1 g* u核心思想
' T- ~1 c. L( c5 T1 K; t1 B
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

/ p% c  B+ u% D+ l8 E
实现代码
3 O. `; D. i% J9 aimport java.util.Arrays;

8 u9 N% u9 o+ O3 o. P6 S/**
* @Author god-jiang
+ v! R$ J# A. Y) a6 Z" u  l* _ * @date 2020/1/13
' f& ]9 ]2 k0 [6 l% I4 e/ p( ?1 R2 F */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
) l2 N" k: a( _public class MergeSort {
0 g: ^& L$ R, h/ l9 v7 q% T) g& U    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
; u3 J' N+ p: x; W, e- }9 O            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
+ y6 Z9 @% @, z  `8 v, a        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
2 q( g6 \3 F- `; |        Merge(arr, start, mid, end);
    }
/ N1 n  W% ]& n/ w- ^* d
    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
' Z4 K/ @8 c2 `5 |* @        int p1 = start;
5 |2 B6 E0 P- p2 c+ z        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
4 J3 V+ ]0 b" b% M2 A: E! b            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
0 F. N% }1 }% D9 `. {& `            } else {
' v+ K# G# M, W5 |4 h                temp[p++] = arr[p1++];
            }
1 v! z# g4 l5 r7 I$ u        }
        while (p1 <= mid) {
* f- R5 F4 Y2 W0 H            temp[p++] = arr[p1++];
        }
) z! i# S1 y% l5 ?        while (p2 <= end) {
! U4 H: B' I/ `! W" q$ ~1 D/ B            temp[p++] = arr[p2++];
        }
3 @& Y/ \( `* J$ [        for (int i = 0; i < temp.length; i++) {
7 V: y) v# l' R4 M6 m            arr[i + start] = temp;
# u0 y& [: w+ J, ^7 R  E- y% p" C        }
* [4 I, `7 m3 h  U% y! N" U    }

    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));
7 A. K2 S, a# H    }
: h7 I5 B* O1 H9 y4 E' a) H}


: m' y" ~+ z6 U* R运行截图
' U  O; B5 K  l+ }' K+ q
! O& v8 H: L- S; a1 Z, P% x

1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
1 @2 C( }" J* f; {& W" ^$ o: _2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
: r4 `, t% L5 h原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

. s6 r' D3 c+ T, d, y3 B
  m7 f# _6 c: ~