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

杨利霞

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

归并排序的介绍

# p* p6 b% |8 C1 o* F. B- i8 i# ^, n归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
: B; M% q/ C- X0 i6 T+ x" R% X. H概念

# m& t  \: k% `1 Q& S( X, x6 W9 p! v4 @是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
/ e' j& h( U% {4 j+ \5 t
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
8 m1 X* e# Q$ N9 ^

3 J0 R& I, T$ s3 Q实现代码
) F$ [3 z; d! @; Pimport java.util.Arrays;
8 v5 p, |- O; r* X5 e8 T. S- D4 {
/**
, k8 w) A" ~+ T * @Author god-jiang
* @date 2020/1/13
8 |+ m% ~* j% p8 t */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
; ^/ ]8 l4 X" Q    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
- |9 c& Q. {; L% k0 X; T# r1 z- I        if (start >= end) {
            return;
        }
        //保证不溢出取start和end的中位数
6 q+ ~5 G+ O4 O+ g9 ]: Y! A        int mid = start + ((end - start) >> 1);
' q8 G5 H1 o7 Z* r; g/ f5 w        //递归排序并且合并
        MergeSort(arr, start, mid);
7 ]. s" v, |5 W& s: t$ z* p        MergeSort(arr, mid + 1, end);
' W/ W4 i0 c/ v" b* Q! D, I        Merge(arr, start, mid, end);
    }

" T. j! g. v8 @  U    //合并
/ I3 i3 e% ~2 U# E; J: }# d0 _    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
- c: D" e- E# ?3 ]1 c& h2 P+ L        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
8 V1 z0 n2 |9 y% h                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
            }
4 E- A. }. o& U9 S4 c        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
5 [$ {; ^9 r6 Y        }
% B" O1 W, m- z- k& _0 K0 z: q        while (p2 <= end) {
            temp[p++] = arr[p2++];
4 Y2 A/ N' U% S. W' W        }
        for (int i = 0; i < temp.length; i++) {
$ h: U; f4 u1 G            arr[i + start] = temp;
) h9 G: Y4 }' K, w8 l7 m; M        }
    }
. O1 M2 }: Z. y, R2 g
; \# S$ }% o9 j6 F    public static void main(String[] args) {
; g5 z, T! E4 _+ N        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
( F0 Z- S/ {* J- I* |6 u        System.out.println(Arrays.toString(a));
& G/ f8 @! Z; o* W" Q! S% Q$ e  s    }
( M( K. N* n' u! E$ T& K6 y: k( ?! Y}

. b8 U2 ]# N# Q& D5 G( h! v! l
运行截图

3 p, {! ?3 s6 {0 O/ s/ q+ c
4 d; W) @* a; @6 p6 G; P* @( v
. ~# W( R! X! G/ A: L1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
1 {+ M' K( T: w, W7 f6 t% L7 T3 V9 d。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035

' C+ j6 M5 {+ [# d" x
' R0 p3 w! ^: ], P4 H; c8 G5 z