归并排序

 1/**
 2 * 归并排序的Java实现
 3 * <p>
 4 * 归并排序的思想是分治+递归。若要将数组排序，归并排序的思想
 5 * 就是将数组拆分为2个不同的数组(一般是从中拆分)，然后分别将2个数组排序，
 6 * 最后将已经排序的数组合并
 7 * </p>
 8 *
 9 * @author wangy
10 * @version 1.0
11 * @date 2021/7/6 / 19:46
12 */
13public class MergeSort {
14
15    static void sort(int[] a) {
16        int l = a.length;
17        sort(a, 0, l - 1);
18    }
19
20
21    private static void sort(int[] a, int p, int r) {
22        if (p >= r) return;
23        int m = (p + r) / 2;
24        // 分治
25        sort(a, p, m);
26        sort(a, m + 1, r);
27        // 合并
28//        merge(a, p, m, r);
29        mergeBySentinel(a, p, m, r);
30    }
31
32    private static void merge(int[] a, int p, int m, int r) {
33        int pos = 0;
34        int left = p;
35        int right = m + 1;
36        // 需要额外的空间
37        int[] tmpA = new int[r - p + 1];
38        while (left <= m && right <= r) {
39            if (a[left] > a[right]) {
40                tmpA[pos++] = a[right++];
41            } else {
42                tmpA[pos++] = a[left++];
43            }
44        }
45        // 分治数组是否有剩余元素，若有，全部添加到tmpA末尾
46        while (left <= m) {
47            tmpA[pos++] = a[left++];
48        }
49        while (right <= r) {
50            tmpA[pos++] = a[right++];
51        }
52        // 将缓存数据写到原始数组中「对应的位置」
53        // p, m, r
54        /*for (int i = r - p; i >= 0; i--, r--) {
55            a[r] = tmpA[i];
56        }*/
57        // 等效代码
58        for (int i = 0; i < tmpA.length; i++) {
59            a[p + i] = tmpA[i];
60        }
61        // 打印合并的过程
62        System.out.println("merge ---" + Arrays.toString(tmpA));
63    }
64
65    // 为2个分治数组分别添加哨兵
66    public static void mergeBySentinel(int[] a, int p, int m, int r) {
67        // 2个数组分别多申请一个空间，用来放置哨兵
68        int[] leftArray = new int[m - p + 2];
69        int[] rightArray = new int[r - m + 1];
70        // 拷贝元素
71        for (int i = p; i <= m; i++) {
72            leftArray[i - p] = a[i];
73        }
74        for (int i = m + 1; i <= r; i++) {
75            rightArray[i - m - 1] = a[i];
76        }
77        // 放置哨兵
78        leftArray[leftArray.length - 1] = Integer.MAX_VALUE;
79        rightArray[rightArray.length - 1] = Integer.MAX_VALUE;
80
81        // 合并元素
82        int li = 0, ri = 0;
83        int pos = p;
84        while (pos <= r) {
85            // 哨兵元素的目的在于，始终可以保证2个分治数组的元素遍历完毕
86            if (leftArray[li] <= rightArray[ri])
87                a[pos++] = leftArray[li++];
88            else
89                a[pos++] = rightArray[ri++];
90        }
91    }
92
93    public static void main(String[] args) {
94        int[] a = new int[]{3, 7, 2, 15, 9, 13, 1, 24, 77, 16};
95        System.out.println(Arrays.toString(a));
96        MergeSort.sort(a);
97        System.out.println(Arrays.toString(a));
98    }
99}