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

杨利霞

% |: @6 _- t6 z/ v
' l9 l0 }* O9 L1 ?神级基础排序——归并排序
4 F5 l; I! p2 o) f" @
% ]( u3 j2 G7 R4 v归并排序的介绍
% f3 f: D! N5 [' g. X2 K) D: M
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
: [7 y0 \4 U' D" a. F# w概念
" @% L6 \1 Z; s. }
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
" e- w' \- T3 }' @4 a: M! |核心思想

9 x8 h8 v8 b: u+ f将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
+ _; r$ c- |+ f" o2 _
6 J: i/ F; ?/ z5 k: p( k" Y
- b9 W0 V: R! F( S实现代码
import java.util.Arrays;
& ^- z: c, R4 [: ?
/**
* @Author god-jiang
* @date 2020/1/13
*/
, }! e8 G/ Y$ l3 N/ d& ?  c: R//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
: L* O8 c& `$ e8 k3 Npublic class MergeSort {
/ g7 N& C" R- G  t: d    public static void MergeSort(int[] arr, int start, int end) {
7 \$ F4 {/ C; Z$ e5 d, [        //分治的结束条件
        if (start >= end) {
            return;
) H- S' x7 ~; N: g7 R& E. m        }
        //保证不溢出取start和end的中位数
$ e2 b; k" h7 i4 R  e! k8 T        int mid = start + ((end - start) >> 1);
0 F& s: r' U) ], d8 ~. W* ^        //递归排序并且合并
3 T0 O& `* X# R6 T% R( j9 G        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
4 I0 t5 M3 ^% D; s* v5 l        Merge(arr, start, mid, end);
    }

: K6 B% v2 m+ T+ y. x    //合并
6 E4 }" h, F' s, ]    public static void Merge(int[] arr, int start, int mid, int end) {
/ K3 R$ X" U! Q; i+ L5 g1 s% y" Q        int[] temp = new int[end - start + 1];
6 Y5 s6 B# B7 C( l: \" _& i! W        int p1 = start;
        int p2 = mid + 1;
  u! s: z+ |) O, X3 A        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
* z2 m, E" Z+ z# `8 r                temp[p++] = arr[p2++];
* I. }' R) \$ ?. _- x5 j            } else {
                temp[p++] = arr[p1++];
            }
1 q3 X, ~$ z* i        }
        while (p1 <= mid) {
" p$ z$ x2 k0 Q+ c5 L( U            temp[p++] = arr[p1++];
        }
0 [2 H5 s9 P5 h* ~        while (p2 <= end) {
            temp[p++] = arr[p2++];
4 `- Q( \9 F- S        }
. k4 r, s  }- E9 I        for (int i = 0; i < temp.length; i++) {
7 c  S, P+ u  U            arr[i + start] = temp;
        }
$ E$ C+ A: p- Z, @# F& o& Q    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
/ X1 p" M7 O7 x/ G4 F/ i6 d        System.out.println(Arrays.toString(a));
    }
- `/ i5 ^) \- l' n9 V, D& M}

: D' y7 Y1 [. O, X/ e
. C2 ]" q/ E4 }  m% _4 Q$ s运行截图
; z+ t6 Y  g9 ^! v' ]


1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
8 z5 D8 O; J5 E3 d% _0 V, J2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
/ F. D. \2 N9 z! \! z' L) L。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
8 U# O" U- R# j