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

杨利霞

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

归并排序的介绍
+ i# W2 P  r* C4 t# p/ ?# V  Q
( F" O  \* h3 f9 J" [2 V归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
( I4 z: r- U+ \概念
  H0 s8 z9 Q" g6 [5 J
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
; y# o# j. b: W8 S( {6 I& h
将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。

& p: v" _+ H3 H1 V! ]- Q
实现代码
" `9 r- }. u6 g- Dimport java.util.Arrays;

  V# W1 U6 L( H: H; }: ]/**
* @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
' }  K: m) ^  _/ ]9 O7 f, b& [    public static void MergeSort(int[] arr, int start, int end) {
1 X: I1 B5 R9 A        //分治的结束条件
        if (start >= end) {
            return;
2 `' S% g, f3 x; p        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
& g% X4 W2 r: a# M9 V0 H5 K  a        Merge(arr, start, mid, end);
    }

9 w: A& Z( [! X8 b. p1 x    //合并
+ ~# s& K$ i% @0 D4 H6 X) Z& O5 Y: V    public static void Merge(int[] arr, int start, int mid, int end) {
/ [+ I" f9 c& }- g* W2 A# ~  }        int[] temp = new int[end - start + 1];
" f+ m: E' B1 u3 A, B/ f+ E# G        int p1 = start;
6 ~4 |. P/ x. \6 N        int p2 = mid + 1;
& g9 `" {, _: E4 T* X7 F* b' u        int p = 0;
        while (p1 <= mid && p2 <= end) {
& {3 L" q2 n4 ^# Z            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
            }
+ p( @) D" ?/ X! @5 O) J/ _, x        }
+ j/ H- s* m8 ]+ I9 x0 q        while (p1 <= mid) {
" K7 \1 K  @9 N& E            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
& g) G5 i3 Y/ K& f3 F" _7 o+ O            temp[p++] = arr[p2++];
        }
+ t  C6 s: W) {" d- z* ?! C        for (int i = 0; i < temp.length; i++) {
; T4 l% H% _9 r/ h/ y6 {            arr[i + start] = temp;
        }
. E2 x* e- l" X    }

, G  S  [* ?' \/ r, h2 j    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
( J. k) Y1 @& w) a  |& |6 ~" U* W        MergeSort(a, 0, a.length - 1);
, W( K/ w' @0 w; C5 h6 M0 O$ ]( I        System.out.println(Arrays.toString(a));
' F# v! ?+ ?4 \$ F    }
}
1 f% a2 A7 I+ z+ ]. Y  n& y$ `! g

0 w- c% w1 v8 M: U) i运行截图
0 q6 _  z6 B: p+ z$ L- [/ `4 w
) T0 j' [  I- E0 \9 F3 i( D
) \5 G/ T7 W' X" O
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
1 ~1 U8 c5 d9 v+ [。
! m! T2 W+ d' M! A5 ^& p原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
6 w. q( I' y# o9 F  H5 t3 N) V) n
) L, F& `) i: i/ a7 l' Z
6 C$ E6 I& u- O% y8 k! H0 X- ]