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

杨利霞

0 q2 Z# ]% l7 K神级基础排序——归并排序
  r4 w  R3 p! e% B
归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
2 Y$ W  m+ e# [0 ^+ s6 K概念
4 ?0 v. A0 H& e- O% O6 S
. \" M! D& S) @$ \  R( I: D是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
. x% N( S$ n! H. L+ e核心思想

将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


实现代码
8 @# G; ^, e7 |+ t/ |import java.util.Arrays;
3 F( |. Y% [( r# m( w
$ H1 g# E7 w& F" k/**
7 i6 ^) \* W- Y$ u5 R) d+ v * @Author god-jiang
# P( l0 e, J' W0 z+ T' i+ U' D * @date 2020/1/13
*/
$ h  Y1 c: R9 D  `//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
% W% K0 r5 [! @. O/ t6 `        }
        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
+ H+ @) }; w) j3 h. h        //递归排序并且合并
        MergeSort(arr, start, mid);
/ }2 m4 ~; h' i" ^        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }

    //合并
  g' h6 l6 ^/ c9 ^& V2 M& R    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
! m: A( W+ k8 H; t) R  e            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
" g" G% b4 {; ?5 g+ g+ A) R- m1 f                temp[p++] = arr[p1++];
* }% B% c% _8 z8 ]. C$ H            }
        }
9 h- o1 D2 |* e% O! ^% I' \# [        while (p1 <= mid) {
1 Q( h$ b% w& m( E3 P# J            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
; \7 o" O5 @- m            arr[i + start] = temp;
        }
' i( C( v" z, }, l& V* A# ~    }
: x: p+ _- ~$ i- A* e
, W0 V1 q+ d# Z/ X  D/ f$ C7 X    public static void main(String[] args) {
. k# h6 j  T3 l& ?( R' ?- Q        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
6 E7 J! u; R, [3 l7 U, o        MergeSort(a, 0, a.length - 1);
! y6 z8 F6 _! X        System.out.println(Arrays.toString(a));
    }
4 j% A. B' W8 c. [4 _( i! c}
. S! F0 D$ X- L3 y
" B3 z2 P6 v/ a( |' c
运行截图
% I0 v/ Y, F! g


8 }! B5 A1 P- k6 l) w3 l( w1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
' W- K7 f; A. Y原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035