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

杨利霞

神级基础排序——归并排序
2 V+ l% x, s. i. v- X! Y0 a5 z
归并排序的介绍

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

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

4 V. V; `+ G8 P& u将两个有序的数列合并成一个大的有序的序列。通过递归，层层合并，即为归并。
. S; t: E& J& X) c* C6 p9 L: G) T

实现代码
; ?) W0 @) D% M' Z% ~4 `0 }  Kimport java.util.Arrays;
# [5 j7 m" h  }8 R1 N7 F4 N5 u2 K
/**
* @Author god-jiang
* @date 2020/1/13
*/
/ N/ g( F( {) _: O1 W- ~//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
public class MergeSort {
    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
+ V. n+ s% L# U* m2 D' g6 H% ~- `        }
        //保证不溢出取start和end的中位数
; u. Y2 x  w! T: W& }; g        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
" \0 B  ~; N: a* p+ \5 n        MergeSort(arr, mid + 1, end);
9 T/ L8 v% q% S9 B* R& Q        Merge(arr, start, mid, end);
    }

4 S: |* {! f* q1 }% M5 h: v    //合并
, ]" f- [4 S# U$ l! X- E% 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) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
" f6 o. z$ k/ g5 w9 Z# L; }# f                temp[p++] = arr[p1++];
8 B5 l; M6 l. L            }
        }
5 R9 D) P  Q* e( o        while (p1 <= mid) {
. S& R4 O* d: q+ G( d            temp[p++] = arr[p1++];
6 ]+ _" W* ^  f) u        }
        while (p2 <= end) {
2 s# z( z3 G1 z7 y5 B. l2 `            temp[p++] = arr[p2++];
! ]# c/ n6 R+ I        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp;
. m* ~3 f0 U( i% l. C5 n        }
) ]2 r2 o/ l3 B" Z/ u7 B    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
6 q) Y+ s8 _# @) G        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
/ G" U) n$ q2 ?) L$ v3 a# t    }
7 C* Z' H# w3 @3 V5 [, `}
3 o) n# C5 N# F2 k, F  R

+ Y( E# b' r! k/ W, p+ f4 a运行截图

; a, ~: F5 }5 i$ S5 f+ c- B
2 E  {7 ?4 u, q" e
3 n1 ~& f4 S1 s8 A" K0 a; E; F1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
7 q/ i5 `  o, p% v2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
。
0 A3 G: T& ^' ]3 L! U原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035