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

杨利霞

$ y5 l: h: d0 l+ f2 Z
神级基础排序——归并排序
$ @$ m, v, R! b; }" ^
* D$ S) W4 ^! d( B3 B3 a归并排序的介绍

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

是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
核心思想

/ Z6 ]# p4 Z  \( X% E5 ]! d0 l( ?将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


实现代码
) a* V0 A1 O% l% B# @import java.util.Arrays;

/**
+ _2 P! v+ @; V# q6 e. W* M. f0 o * @Author god-jiang
* @date 2020/1/13
*/
+ C$ N# w7 {; i! E7 D//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
  c4 F) S: w2 @4 v+ l! C) ?8 \            return;
% S8 C* _. }3 y& D        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
4 ~/ R  D1 ?& E7 n: j. |    }
& J5 g8 `( a- s: W
' J+ ?% b0 b  \" k, }& W9 p    //合并
    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
/ i' R+ b5 ^* {+ j6 [! Z& ~! l. ~        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
3 }) G$ J5 C! _7 P) `4 B! R                temp[p++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
& J# l/ B) N- O0 L+ x0 {            temp[p++] = arr[p1++];
  s6 B: M/ r, l7 X        }
* C+ T  E4 r8 c: ]7 D        while (p2 <= end) {
1 F; v( z$ h  W2 {8 E            temp[p++] = arr[p2++];
: J0 Z' Z9 k! \2 T. d2 f% f% Y$ |        }
2 ?! T: H8 i3 q4 \5 M# g        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
8 \. E1 u+ e; v8 x3 I4 l5 O        }
- s* Y' z& z, f5 b    }
% S- ^+ L9 E) K( d# G* S( P# w/ S
    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
. {, ^. O, Z" I

) B: X, [4 b$ ]" E* Y运行截图
; b. v( }# P4 \: n8 f
3 W  G; ?" Y, P5 b( l* G
: k! H) M$ c6 l( I$ d; U) u
1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
: y4 d3 C4 F8 w' h) l& K3 f* _# g。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
& O, B* q  |. I% Y6 H/ r
( o# I4 V0 f# F8 R5 f/ `
- M# D4 v9 d1 s2 c: E7 |