算法笔记-归并排序

1、归并排序是什么？

归并排序采用的是分治(divide-and-conquer)法思想。

基本思想是将一个集合递归分成两个集合，对每个集合内的数进行排序，最后再把排好序的集合再次排序

2、归并排序执行图

先来看归并排序的大致过程，这个是为了方便看，是这样的

可以将他的执行过程理解为一颗二叉树，每个数的子节点都是父节点对半分的集合，对每个子节点进行排序之后，再对父节点进行排序

3、Java实现归并排序的框架

以[8,4,5,7,1,3,6,2]为例子

/**
 * @author 我见青山多妩媚
 * @date Create on 2022/6/23 9:23
 */
public class Sort {
    static int count = 0;

    public static void main(String[] args) {
        int[] arr = new int[]{8, 4, 5, 7, 1, 3, 6, 2};
        mergeSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    /**分割成小区间
     * 继续分割区间，直到分割到不能分割为止，然后往下走合并两个区间
     * @param arr 数组
     * @param left 左边界
     * @param right 右边界
     */
    public static void mergeSort(int[] arr, int left, int right) {
        //先判断分割的区间是否合法
        if (left >= right) return;
        int mid = (left + right) / 2;
        //分割左区间
        mergeSort(arr, left, mid);
        //分割右区间
        mergeSort(arr, mid+1, right);
        //对两个区间排序，合并两个区间
        merge(arr, left, mid, right);
    }

    /**
     * 对每个小区间进行排序，合并两个区间
     * @param arr arr
     * @param left  左边界，左区间[left,mid]
     * @param mid  左右区间分割界限
     * @param right 右边界，右区间[mid+1,right]
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        //临时数组，用于存放排序过后的数，长度为左右区间总长度length=right-left+1
        int[] temp = new int[right - left + 1];
        //i为左边区间开始下标[left,mid]，j为右边区间开始下标[mid+1,right]，k为临时数组下标
        int i = left, j = mid + 1, k = 0;
        //当length=2时，判断的是两个相邻的数大小，当length>2时，判断的是两个已经排好序的区间大小，可以自己debug看一下具体过程，挺有意思的
        //每次判断都是把小的加到临时数组内
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        //如果其中一个数还没区间分割点，那么说明上一个while循环已经把满足的全部加到临时数组了，那么把没有遍历完的一个区间按顺序加入临时数组即可（因为是排好序的）
        //左区间加入
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        //右区间加入
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        //将排好序的值依次重新赋给原数组，left+t为该数组本次开始遍历下标
        for (int t = 0; t < k; t++) {
            arr[left + t] = temp[t];
        }

    }
}
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

运行结果：

1 2 3 4 5 6 7 8 
1

4、时间复杂度分析

**附：**关于归并的一个算法
力扣-数组中的逆序对