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

杨利霞

( E, M+ Q6 e! c! z( g* |
. h) `8 j, I: b- e" ?1 Y9 D神级基础排序——归并排序

$ x: Y1 M9 }% j, j6 r0 y归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念

) l0 k/ Y' B/ v# Z1 G6 L0 t6 E' [4 c是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
8 R" a5 P3 x* G0 K. H
, H4 ]" M1 ?7 j7 x; R将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

9 z: c: @! ?6 Z4 Z9 R
实现代码
3 y0 ]' y  A- }" y6 N, X) }) s( l' Uimport java.util.Arrays;
3 ^* g, l0 O, `7 Z' K' c! a* D! b
8 R3 g3 U/ h8 z/ h) M5 j# ~% T/ k/**
* @Author god-jiang
* @date 2020/1/13
+ u2 @: J& ~2 C( q */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
3 ^: v8 T; ?3 W- O        if (start >= end) {
            return;
: a( F% W5 n& j% R0 V) ?: x        }
" w) m4 x$ D# c/ B        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
7 m  \6 r. j6 S% b        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
9 a7 l  E7 s4 `+ y: M        int p2 = mid + 1;
0 S; u$ g, L1 x& L. g" t5 L        int p = 0;
! ]3 u0 ?% a' G3 M8 C  _        while (p1 <= mid && p2 <= end) {
4 U& J9 p6 b6 i, M0 M            if (arr[p1] > arr[p2]) {
$ U# H& ~6 Q7 g2 ^" \; X) ~                temp[p++] = arr[p2++];
' o- s& E. W% {$ ~* c* ?            } else {
# K1 t$ J0 U5 G1 F                temp[p++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
% C" l! j- M  c7 H            temp[p++] = arr[p1++];
        }
6 U; @8 \8 Y  x' E  e        while (p2 <= end) {
            temp[p++] = arr[p2++];
( J4 i0 P- H  [( w& B# u# \, s        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
        }
) E! t6 X, O, p: y    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
( @- \: O* c4 g. R& d) H- X1 l, B9 R        System.out.println(Arrays.toString(a));
& g. s8 T9 V" c5 I6 U    }
}
; X5 S" B% {5 ]* x6 }( y' Z
2 K1 q* s* H  v6 c7 g
运行截图
- l' H% y& S+ v+ B# c! l

( V4 N; N7 u' |  X% u6 h
' D0 p; ]# J4 c( H1 N) ]1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
9 S, b, H. A1 d* g% Q! y。
) ~1 H4 v5 C. }. c( B" p# x原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035


0 p/ H  n# c- P$ N( L( B6 }  D