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

杨利霞

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

归并排序的介绍
7 N! Q  Y* p* _
归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念
; R) Y$ h7 c4 I$ @& k
是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想
# I7 |5 D1 G( u
. p) o4 O7 z+ \* W' w( u0 {将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
) [0 X2 F9 N! s3 m

实现代码
import java.util.Arrays;

" c) q" T0 U0 }/**
* @Author god-jiang
* @date 2020/1/13
*/
5 o3 w: o4 t, V: j//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
& x9 |4 y. u6 c5 zpublic class MergeSort {
1 {' g$ E7 x4 m+ \0 }, Z    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
& J# I; L9 g  r6 X8 i            return;
0 T' E1 r5 i. Z        }
6 ?; b$ ~) O- D, R5 Q        //保证不溢出取start和end的中位数
$ W% B+ ~, T  k* c3 C        int mid = start + ((end - start) >> 1);
2 t- v- \& ?# o, R: _& ]        //递归排序并且合并
        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) {
4 o3 X3 ]) f0 A3 H9 K        int[] temp = new int[end - start + 1];
/ Y; B3 |- ?3 ^) o  i, t        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
# K* Q7 C, B4 E4 _2 A% C        while (p1 <= mid && p2 <= end) {
7 L; M$ U  T8 M7 W8 W0 G. A& S- d* X            if (arr[p1] > arr[p2]) {
& L% u' }# n. b( L# y. e5 J' Y3 {                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
            }
        }
& D. u: `" y9 @( q- M% a, S        while (p1 <= mid) {
- Z7 a) O! z) H$ t$ p8 g; W            temp[p++] = arr[p1++];
        }
( Z6 p+ b  ^3 Z1 Y" A3 e        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
7 N% c9 o* R' b        for (int i = 0; i < temp.length; i++) {
8 ~4 J( g, K, X0 c            arr[i + start] = temp;
: {+ R; i8 P+ N- j# [. j5 _2 `        }
  J% t, E) Y% u7 l5 R    }

1 C. p8 P3 H! K/ ~3 t7 {6 t3 G    public static void main(String[] args) {
( |+ W2 G  }2 j        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
7 i3 s/ h2 F5 h  u; |& W        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}


; H) O0 k' @% N2 Z运行截图

  g4 z8 Z5 x9 o4 X" }" M

1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
/ d8 K3 h4 a8 j5 G原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
5 T/ k* l" o$ F6 C
; c# J+ c% M$ D