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

杨利霞

神级基础排序——归并排序
; c) |( W" g5 F) _1 M
归并排序的介绍

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

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

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


实现代码
) e2 l) h7 G( G& {4 N/ ^import java.util.Arrays;

/**
* @Author god-jiang
* @date 2020/1/13
1 p+ Q) S7 K# `$ ^' S5 q/ V' h */
//归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
) s! k9 M* s' C( ]public class MergeSort {
' N1 E7 O- D8 M6 p; E$ m+ D. H    public static void MergeSort(int[] arr, int start, int end) {
        //分治的结束条件
        if (start >= end) {
            return;
3 M" D3 i9 S& Q3 F        }
        //保证不溢出取start和end的中位数
: z! v: I7 I9 O$ [# b& h5 I' R        int mid = start + ((end - start) >> 1);
        //递归排序并且合并
        MergeSort(arr, start, mid);
4 t' h6 T7 d5 y) ^& Y        MergeSort(arr, mid + 1, end);
0 M5 u# u  J  F1 M        Merge(arr, start, mid, end);
+ k& h4 Z( A) N    }

    //合并
1 f; j2 J6 [& _6 k2 S    public static void Merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
1 Y- a6 g' X, C$ ]4 z        int p1 = start;
. F4 S  I9 s# W& y7 }4 J        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
( A' g! G( h& S. T                temp[p++] = arr[p1++];
            }
        }
8 I5 d  o+ e3 g8 q6 x        while (p1 <= mid) {
9 K0 p; W% _+ B/ a            temp[p++] = arr[p1++];
8 `7 t1 t# C5 X8 q; N; U, f9 N5 \        }
, q. @! [. {, \+ D        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
, L, g  n6 H" f+ b3 y+ N        for (int i = 0; i < temp.length; i++) {
( E0 Q0 e% x% U! V, |9 k            arr[i + start] = temp;
        }
9 t; U# V7 ]& V; g6 I( ?+ ^    }
/ `- I/ M2 n& J' s5 a
9 ^4 d4 }8 Y0 D# b4 r    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
6 {& m* Z# W, l  j+ ^$ V/ r# [        MergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}


运行截图
) ]9 u" x+ m% D$ w) ]


! U/ d6 f; y  }1、以上就是今天分享的归并排序，时间复杂度为O(N*logN)，空间复杂度为O(N)
2、归并排序的额外空间复杂度可以做到O(1)，但是非常难，不需要掌握，有一篇论文”归并排序内部缓存法”可以做到
1 W  x1 {2 b- |, h0 n。
- q( Z0 D, s5 r1 G; }, M# i原文链接：https://blog.csdn.net/weixin_37686415/article/details/105180035