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

杨利霞

神级基础排序——归并排序
! u, N6 Z: s0 G* `
8 K# H+ L* u  b- X3 ]归并排序的介绍
6 w: _2 }: U/ {9 S5 {4 _
8 t" b4 y& B8 M. B; P# ?8 ?归并排序(英语：Merge sort，或Mergesort)，是创建在归并操作上的一种有效的排序算法，其时间复杂度为O(N*logN)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
概念
* C( w7 G. ^; ?9 J3 }
" v: a6 j& p4 l- X4 i是利用递归与分治的技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成越来越大的有序序列。
5 {1 T- ^% s4 I& f核心思想

将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
9 I* ]1 y5 t' c3 R' a2 Y

4 }1 G- U& ^7 q% _9 h. v实现代码
; F1 w1 d; R% r, d) p: Uimport java.util.Arrays;

8 v1 _2 b1 T; z) b7 l, B/**
* @Author god-jiang
* @date 2020/1/13
*/
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
" d# O+ M* y4 N1 ?! c3 \- |' m/ `! I    public static void MergeSort(int[] arr, int start, int end) {
2 j6 T% [5 A- O4 A        //分治的结束条件
        if (start >= end) {
1 ~6 f3 O% q( [5 I7 p) U; F5 |            return;
) N' i' P% Z( k, ~8 R        }
3 g- S2 C8 _6 n3 m" s, [7 X        //保证不溢出取start和end的中位数
        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
) T# Q: Y; P$ P0 \7 @        MergeSort(arr, mid + 1, end);
        Merge(arr, start, mid, end);
    }
; g3 V& j8 Z- _( j6 P2 p
    //合并
# L" y0 \) L+ O; e8 ?9 c3 f. f    public static void Merge(int[] arr, int start, int mid, int end) {
7 P: a$ w6 g" N" u/ ~        int[] temp = new int[end - start + 1];
: j8 m2 X- l0 j2 E1 D1 x6 x: l/ }        int p1 = start;
        int p2 = mid + 1;
. b$ U7 C8 _& r' L& l        int p = 0;
        while (p1 <= mid && p2 <= end) {
/ K: I" D7 ~# K8 Q% R% {/ a            if (arr[p1] > arr[p2]) {
6 b4 e/ b+ r$ l" g6 U- J+ I                temp[p++] = arr[p2++];
            } else {
. S: U. k6 N& y. }& m9 `. |5 ]                temp[p++] = arr[p1++];
$ d) @6 Q, i$ ?            }
        }
0 V; z; ^5 s8 f  o# n        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
! [) V, E; |, u3 q3 R6 C- Q* Y        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
        }
    }
; ]3 V9 x/ T3 e
+ M0 F, E/ i2 }1 c$ j1 w8 W    public static void main(String[] args) {
' k3 S. _" c" w% L5 G" V9 K0 n/ M        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        MergeSort(a, 0, a.length - 1);
% f9 X6 ?5 ?1 p& D' d- v        System.out.println(Arrays.toString(a));
    }
}

$ M: M  t! S9 {/ u8 D2 j, M5 B
运行截图
* r5 `$ U3 k" b+ @' r+ P

+ V2 F" j5 u, y, P; L
/ t" Y  W. |9 @) [5 c1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
+ Y7 Z7 T' s0 A7 \" I1 q5 F$ O/ }2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035
) ~4 Y0 g5 _3 C' j( h. s- e2 X