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

杨利霞

& _% z  m9 O. S神级基础排序——归并排序

% M- n) m! w# r# w& {# E归并排序的介绍

归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
; U* A6 T- ]* x% R9 q1 G概念
& e# {* t' i, I* D% k3 Y
3 R- [) o% X5 w# a是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
3 O) ?; O- s2 A- C- P; u- m核心思想

" @2 V4 q$ }5 E/ C/ L将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。


; Q! C6 K7 J+ l1 @实现代码
4 ^9 N7 g& b5 L, k5 j* _1 yimport java.util.Arrays;
. j4 @& _; }# g* X6 Y8 J/ E
/**
' }8 N& k5 S. B7 E. R. m: }7 q+ t * @Author god-jiang
* @date 2020/1/13
: E( [% r, V  P, k( p3 A$ ^% M */
( A3 x6 L% {# v//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
% q, s7 w! L6 _# M9 ~    public static void MergeSort(int[] arr, int start, int end) {
; ~2 F" o  |% a1 e# m/ ]- X        //分治的结束条件
: ]+ p; q: v; Y) f( z/ X        if (start >= end) {
            return;
        }
        //保证不溢出取start和end的中位数
% i! w7 h5 Q4 a0 |        int mid = start + ((end - start) >> 1);
" Z( H$ _* P9 H. M        //递归排序并且合并
3 t5 i4 }- @* A% H. a  h9 C        MergeSort(arr, start, mid);
        MergeSort(arr, mid + 1, end);
# \$ M- A9 j/ Y6 L) |        Merge(arr, start, mid, end);
! }4 k$ l7 A1 ~( }7 `    }

+ w: u1 S0 a) W* N    //合并
0 [# r: K3 d0 y3 J2 x* t    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
4 L4 M% T- ]6 ]& V" y* F        int p2 = mid + 1;
7 H& y& P% @) M        int p = 0;
        while (p1 <= mid && p2 <= end) {
* M( u8 w* b6 x& `6 C( o; J5 M            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
' _# K  ~, p' S" x. y3 C; [            }
        }
% y; X' y" t- q        while (p1 <= mid) {
8 \# S3 e2 b$ H8 z! ~- ~2 Y4 o4 |- x            temp[p++] = arr[p1++];
/ N4 g# r% W( w) `        }
& _! Z* j3 x+ r! o; W        while (p2 <= end) {
            temp[p++] = arr[p2++];
3 ?7 F' O5 o3 ]8 [        }
        for (int i = 0; i < temp.length; i++) {
* |* Q3 v  L. g! R6 ~$ G            arr[i + start] = temp;
        }
; n0 }6 {! I) \+ p, J- Y9 K    }
2 n2 C! ^# I& `" ~
    public static void main(String[] args) {
9 T+ Q9 C8 u0 Z+ h2 {9 V. o5 S        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
' {/ U, [; ^. m        MergeSort(a, 0, a.length - 1);
  E9 k+ D& L2 V- {        System.out.println(Arrays.toString(a));
) V2 O, h7 S6 E3 P7 I# t  w" r3 I    }
}

  T9 ]1 H1 k4 H$ [$ N% A
运行截图
, P$ I8 d# Y3 F4 C2 J


1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
- a) b: @" w  X原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035


8 |% h5 ^5 _7 a" M