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

杨利霞

: b5 O  N) \, y: k2 n* y
神级基础排序——归并排序

* K+ g7 U+ @  E5 c- S归并排序的介绍
/ k$ Q9 s  ?# q
9 C+ i8 p2 Q6 N5 [$ j归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
3 C- e% e' e& J, J6 x概念
4 q( r0 W8 w* }3 ~5 e
5 U( K- W  T0 o8 A+ r7 X是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想

) x* o0 b1 H" k) g7 f将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

5 }* e% o- P( }' p/ _
/ s5 X* ]/ t. @" |$ B  b/ G实现代码
7 Z3 Q- K# `/ @! \$ w! i& aimport java.util.Arrays;

- x: g  \5 Y' o) S) @% o/**
! }9 ], ?& R# m; t  L7 X- P * @Author god-jiang
* @date 2020/1/13
1 K' F1 A. B9 T2 s; f */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
& [) j- F# c- }7 }public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
3 h$ \6 s- H+ C7 s; z0 X        //分治的结束条件
  P, M5 x8 l; B3 y+ N8 X- T) }        if (start >= end) {
% F$ K; T: e2 o- [5 Y            return;
        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
7 O# P+ Q: P& P; Q- }5 j, s6 \        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
) F7 ]" ^% W* s, U8 W        Merge(arr, start, mid, end);
/ S; {' d6 ]( r    }
) ^0 S- W( u+ |
+ L; p  t5 I7 @9 j5 h    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
, K' H, N1 r' L' ?% n5 m: C        int p1 = start;
. V! f* f1 z3 H; E3 i" L2 _4 h9 U        int p2 = mid + 1;
5 a0 Z1 M0 d4 I3 K        int p = 0;
        while (p1 <= mid && p2 <= end) {
/ t  C" K$ j) A, g7 ]) T            if (arr[p1] > arr[p2]) {
8 _9 R7 P7 d) x* h                temp[p++] = arr[p2++];
7 d& I% {' Y  J; Z            } else {
! R0 l; Z/ K' _% |# h                temp[p++] = arr[p1++];
            }
        }
6 O! V, g, f' ~+ Q$ G        while (p1 <= mid) {
8 E, b3 R( A; X2 }& R7 N* y            temp[p++] = arr[p1++];
        }
  m( W! a1 K- E; @8 H( F9 w        while (p2 <= end) {
3 l6 z4 |; i0 C            temp[p++] = arr[p2++];
        }
( a+ J4 I$ n8 @3 p        for (int i = 0; i < temp.length; i++) {
4 d# O( g3 ]! K            arr[i + start] = temp;
        }
  Q3 o8 w' y4 O* P( Y+ v. O    }

$ [9 P1 h7 M3 f2 G% V) \- D    public static void main(String[] args) {
  S% }4 m8 k( X7 o        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
( Z6 n$ `" X# o: h, q) ]        MergeSort(a, 0, a.length - 1);
6 H* r: ^+ P: M. ~$ O6 D, z) C/ V        System.out.println(Arrays.toString(a));
3 \9 m1 q: {) _5 }1 o    }
- G6 O9 I2 t# N# o}
/ n/ s" o0 U4 u5 j7 d; M

运行截图


: J( N1 M* h( y
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
$ [/ B! a3 J+ O2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
* z; c; j  E% T. d1 Q: L。
9 h$ f$ E7 A% b9 I8 P" b7 }原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035


( `% ?8 C, Z# S+ {8 }/ Y9 S3 J