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

杨利霞

神级基础排序——归并排序
/ C6 _1 R, j5 ]/ ~/ ?( ~
1 T' r) y" x; [! V& z0 \$ n6 W归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
  T3 h4 U& s% C3 q. E概念
  B1 o) y1 _6 N( S& @, C
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
% j/ i8 @( i5 a! }
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

# ^% x7 i/ W+ X8 ?
3 L2 X# b4 L( q实现代码
import java.util.Arrays;

6 L* a' f8 ^% s! i0 v/**
$ @7 c/ y5 `+ f9 U! q2 B' P * @Author god-jiang
* @date 2020/1/13
/ j; B& D! n4 } */
4 O' O% C6 @: u8 Q//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
7 y1 ?' F% m+ W, W: Fpublic class MergeSort {
9 H9 p3 _4 |; P6 g    public static void MergeSort(int[] arr, int start, int end) {
, P4 E' a3 T8 g7 ?        //分治的结束条件
        if (start >= end) {
8 M  @3 \& }& }( L* V: h7 g7 u            return;
        }
4 u1 O) u" i5 W# L7 b1 x9 A! t        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
2 A5 @. r! b5 C/ W( o7 ^        //递归排序并且合并
+ ^% t5 l- H' n5 S; S. d: y9 F9 N7 o        MergeSort(arr, start, mid);
( b- `7 q; ?9 ?: f$ a; `  k9 ]        MergeSort(arr, mid + 1, end);
4 ?& z% _& p! r* B! K/ r2 i        Merge(arr, start, mid, end);
    }
3 l; H1 _$ G( n/ U4 S
3 }, M+ m1 X4 p/ o    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
9 u, V' T  A! R        int[] temp = new int[end - start + 1];
        int p1 = start;
# m/ g( W0 X! `0 G  f) k" b2 l3 C! [        int p2 = mid + 1;
) u7 S! K( X) ?- A( y+ r        int p = 0;
        while (p1 <= mid && p2 <= end) {
, A+ q: ]  Y9 \            if (arr[p1] > arr[p2]) {
) A  \3 @; }8 B3 y  ?6 S  X$ D                temp[p++] = arr[p2++];
            } else {
- V# B" r' q) S/ v' w                temp[p++] = arr[p1++];
# ?! B1 Q5 k- h" O( E4 F            }
        }
; L& e" b8 }* w/ q* s7 w5 ~: g        while (p1 <= mid) {
) r9 R5 p5 x. G            temp[p++] = arr[p1++];
7 E  d* B2 }6 t" ?8 i9 b" A        }
; g0 w  o2 W' ^        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
* s3 |+ j$ G4 o+ D- `1 R        for (int i = 0; i < temp.length; i++) {
* y6 Z. Y, K7 U0 ^) t, Z& @# S- `            arr[i + start] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
  o7 o0 K) }, }! u9 D' V* {6 p% Q        System.out.println(Arrays.toString(a));
# `  o# d' J( m. o3 f% C    }
6 Z( K1 O8 P. U3 b; ]% }4 z0 s}
* c6 Q$ t& m9 P% y& g6 L, u
  `8 z  s  u7 E. W  l* P0 m5 C
, t0 ?' \5 g# a( F# @: D运行截图

, f2 S( n; T! D
: V- X! ]- W: m/ M) @% D& h
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
5 j8 W; l8 ^6 _. J% q原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

. J, Z0 j( S2 A" ]