归并排序及其时间复杂度分析

归并排序及其时间复杂度分析

什么是归并排序？

归并排序体现的是一种分治的想法，将原数组进行拆分，分别排序每个部分，然后再将它们一一合并，最后达成我们想要的结果。

1. 将数组拆分

• 将数组排序

• 怎么排序的（从小到大排序）

代码部分

/**
 * @author `dongxu.kwb`
 * @date `2022/8/30`
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {79,3213,3,5,45,65};
        mergeSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void mergeSort(int[] arr) {

        //判断下数组是否为空，或者是一个数

        if (arr == null || arr.length < 2) {
            return;
        }

        //给整个数组分割并且排序

        process(arr, 0, arr.length - 1);
    }

    /**
     * 主要负责递归
     * @param arr
     * @param left
     * @param right
     */

    public static void process(int[] arr, int left, int right) {

        //递归结束条件

        if (left == right) {
            return;
        }

        //找中点

        int mid = left + ((right - left) >> 1);

        //左右拆分并且排序

        process(arr, left, mid);
        process(arr, mid + 1, right);

        //排序

        merge(arr, left, mid, right);
    }

    /**
     * 主要负责排序
     * @param arr
     * @param left
     * @param mid
     * @param right
     */

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0;
        int p1 = left; //左指针
        int p2 = mid + 1; //右指针

        //如果左右指针都没超出边界

        while (p1 <= mid && p2 <= right) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }

        //左指针超出边界

        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }

        //右指针超出边界

        while (p2 <= right){
            help[i++] = arr[p2++];
        }

        //将排好序的部分同步到arr原数组中

        for (int i1 = 0; i1 < help.length; i1++) {
            arr[left + i1] = help[i1];
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

时间复杂度分析

我们发现在递归函数里，子递归的机会相同。所以可以使用master表达式。

master表达式见文章：https://blog.csdn.net/abaidaye/article/details/126603143

        process(arr, left, mid);
        process(arr, mid + 1, right);
1
2

因为在merge函数中，无论如何，两个指针加起来都遍历了n个数所以d=O(n)。

所以，该题master公式为：T(n) = 2 * T(n/2) + O(n)。

此时 $lo{g}_b^a$ == d, 所以时间复杂度为 O(n$lo{g}_2^n$ )