排序-归并排序

    归并排序是时间复杂度O(nlogn)，O(n)空间复杂度的排序算法。

算法基本思想

  • 对两个有序数组合并成为有序数组，只需要O(n)的时间复杂度

  • 将数组从中间拆分为2个数组，递归拆分，直到只剩一个数字

  • 一个数字本身即为有序的，此时按照合并有序数组的方式开始合并

  • 每次合并的数组本身就都是有序的，因此最后返回的即为有序数组

空间复杂度降低思路

  • 开始定义一个和排序数组长度一致的数组做为临时储存使用，这样就不用每次都创建空间了

  • 无法进行原地排序，如果使用原地排序后即变为插入排序

  • 归并排序也为稳定的排序算法

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
private int[] mergeSort(int[] arr) {
    int[] tmp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, tmp);

    return arr;
}

private void mergeSort(int[] arr, int start, int end, int[] tmp) {
    if (start == end) return;
    int middle = (end - start) / 2 + start;

    mergeSort(arr, start, middle, tmp);
    mergeSort(arr, middle + 1, end, tmp);

    merge(arr, start, end, tmp);
}

private void merge(int[] arr, int start, int end, int[] tmp) {
    int middle = (end - start) / 2 + start;

    int start1 = start;
    int end1 = middle;


    int start2 = middle + 1;
    int end2 = end;

    for (int i = start1; i <= end2; i++) {
        if (start1 > end1) {
            // 只处理第二段
            tmp[i] = arr[start2++];
        } else if (start2 > end2) {
            // 只处理第一段
            tmp[i] = arr[start1++];
        } else if (arr[start1] > arr[start2]) {
            // 比较后处理2段
            tmp[i] = arr[start2++];
        } else {
            // 比较后处理1段
            tmp[i] = arr[start1++];
        }
    }

    for (int i = start; i <= end; i++) {
        arr[i] = tmp[i];
    }
}