排序算法——归并排序

发表于 更新于 分类于 ， ， ，

介绍

归并排序(MergeSort)，是采用分治思想的一种算法，通过把要排序的数组依次递归对半拆分，当子数组达到长度1时，即只有一个元素，认为其为有序的，结束递归。使用递归排序时，无论原数组序列的排序情况如何，都要递归到最底层，所以时间复杂度相对固定。为\(O(nlog(n))\). 归并排序可分为二路归并和多路归并，最常用的是二路归并，下文示例亦是针对二路归并排序的。另外，归并排序是稳定的。

图解

拆分阶段：

image-20210509204359870
image-20210509204359870

合并阶段：

image-20210509204925849
image-20210509204925849

示例代码

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
def mergeSort(arr):  # 拆分
    if len(arr) // 2 == 0:
        return arr
    return merge(mergeSort(arr[0:len(arr) // 2]), mergeSort(arr[len(arr) // 2:]))


def merge(a_l, a_r):  # 合并
    a = [0] * (len(a_l) + len(a_r))
    p_l, p_r = 0, 0  # 左右数组的左右指针
    while p_l < len(a_l) and p_r < len(a_r):
        if a_l[p_l] > a_r[p_r]:
            a[p_l + p_r] = a_r[p_r]
            p_r += 1
        else:
            a[p_l + p_r] = a_l[p_l]
            p_l += 1
    while p_l < len(a_l):  # 若左数组剩余，依次填入
        a[p_l + p_r] = a_l[p_l]
        p_l += 1
    while p_r < len(a_r):  # 若右数组剩余，依次填入
        a[p_l + p_r] = a_r[p_r]
        p_r += 1
    return a


if __name__ == '__main__':
    a = [16, 55, 64, 35, 24, 4, 85, 68, 84, 41]
    out = mergeSort(a)
    print(out)
    
[out]:
[4, 16, 24, 35, 41, 55, 64, 68, 84, 85]
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
import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{97, 76, 84, 35, 60, 53, 59, 62, 93, 53, 37, 19, 9};
        arr = mergeSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }

    }

    public static int[] mergeSort(int[] arr) {
        int len = arr.length;
        if (len / 2 == 0) {
            return arr;
        }
        int[] arr_l = mergeSort(Arrays.copyOfRange(arr, 0, len / 2));
        int[] arr_r = mergeSort(Arrays.copyOfRange(arr, len / 2, len));
        return merge(arr_l, arr_r);
    }

    public static int[] merge(int[] arr_l, int[] arr_r) {
        int len_l = arr_l.length;
        int len_r = arr_r.length;
        int[] arr = new int[len_l + len_r];
        int p_l = 0;
        int p_r = 0;
        while (p_l < len_l && p_r < len_r) {
            if (arr_l[p_l] < arr_r[p_r]) {
                arr[p_l + p_r] = arr_l[p_l];
                p_l++;
            } else {
                arr[p_l + p_r] = arr_r[p_r];
                p_r++;
            }
        }
        while (p_l < len_l) {
            arr[p_l + p_r] = arr_l[p_l];
            p_l++;
        }
        while (p_r < len_r) {
            arr[p_r + p_l] = arr_r[p_r];
            p_r++;
        }
        return arr;

    }
}
[out]:
9
19
35
37
53
53
59
60
62
76
84
93
97