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

杨利霞

& q% Y0 @4 y1 _! i! \4 }' w: w9 p3 x
神级基础排序——归并排序
; Y4 o) ]6 [& j2 h
/ p7 \/ ?4 `& d: S1 k0 h' h2 K归并排序的介绍

8 W+ j. b4 H) }' b/ V# q归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
' F9 I6 x* b9 H概念
+ s4 x( s- D, f& i. T, {
, ?6 u/ d, U6 n2 f& |, [8 _是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
7 M" H( Y6 s/ R+ H
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

, k6 M/ d3 B' j2 W! S. j
, U# P: k7 w$ n; D5 X实现代码
import java.util.Arrays;
# l. G" h/ k& q4 v6 c* }) e
/**
* @Author god-jiang
9 O) F) H1 x9 X! T8 D * @date 2020/1/13
*/
  G% P0 M* H# E% @( k//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
$ e' _! y3 l/ b1 K; ]public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
+ G0 |, w6 ]: K6 N            return;
        }
        //保证不溢出取start和end的中位数
# U  G$ W+ _- I        int mid = start + ((end - start) >> 1);
% L; h" w3 W. X/ N# ]1 C7 ]( ^        //递归排序并且合并
3 W5 J9 L( {, ~1 }- {& X% W        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
) d. x: D( _0 z5 b    }

5 f4 r* K" [- R" K: ]* d    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
5 C" y) d6 z- m* i2 V& o2 r        int p2 = mid + 1;
+ R3 Z8 o. ~* y1 ^. ?        int p = 0;
4 p* Y; t: \) m; s" q8 S2 Q1 [  R* \        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
/ q" h+ ?9 M% v7 v  {            }
+ W5 `# f! V, @. m! E+ q        }
6 D" K8 z4 r* K3 w; B: T        while (p1 <= mid) {
            temp[p++] = arr[p1++];
  Y3 V$ Q" S/ P6 d7 `& Z' R        }
5 D: u  o+ f( Q! J- R7 R# H7 P; D" ]        while (p2 <= end) {
            temp[p++] = arr[p2++];
/ D* c( }& p; |# I# L        }
        for (int i = 0; i < temp.length; i++) {
, R0 J7 j* W. r; V* _, ?            arr[i + start] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
( Z3 o3 q( r$ k* H/ F# {! w        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
2 I+ f5 ~: q! R    }
}
2 q5 b- m% ~; j. h" b8 F0 G

- b( F* G' O3 ?6 N; v$ Y6 d运行截图
( T+ h/ B# M$ W4 a# C& s0 D& h6 n

$ m( p) s4 c9 Y
6 U! q: a0 H5 D1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
, L' s0 M  q9 t, q2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
4 T0 g: ]% J+ [. Y& d原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

: `5 b7 p# N& R
8 C# g( I# ~- i0 V8 ?6 q! p" D/ h