0%

归并排序

发表于 更新于 分类于

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。

基本思想

  1. 把长度为n的输入序列分成两个长度为n/2的子序列
  2. 对这两个子序列分别采用归并排序
  3. 进行递归

动态图如下(来源：https://www.cnblogs.com/onepixel/articles/7674659.html)：

sort.jpg

代码实现

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;
import java.util.Comparator;

/**
 * @author gelong
 * @date 2020/6/4 23:34
 */
public class MergeSort {

    public static <T> void sort(T[] data, Comparator<T> comparator) {
        sort(data, comparator, 0, data.length - 1);
    }

    private static <T> void sort(T[] data, Comparator<T> comparator, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >>> 1;
        sort(data, comparator, left, mid);
        sort(data, comparator, mid + 1, right);
        if (comparator.compare(data[mid], data[mid + 1]) > 0) {
            merge(data, comparator, left, mid, right);
        }
    }

    /**
     *  合并[left, mid] [mid + 1, right]
     * @param data 数组
     * @param comparator 比较器
     * @param left 数组1 左边界
     * @param mid 数组1 右边界
     * @param right 数组2 右边界
     * @param <T> 泛型
     */
    private static <T> void merge(T[] data, Comparator<T> comparator, int left, int mid, int right) {
        T[] aux = Arrays.copyOfRange(data, left, right + 1);
        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                data[k] = aux[j - left];
                j++;
            } else if (j > right) {
                data[k] = aux[i - left];
                i++;
            } else if (comparator.compare(aux[i - left], aux[j - left]) < 0) {
                data[k] = aux[i - left];
                i++;
            } else {
                data[k] = aux[j - left];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }

}

我们还可以用迭代的方式进行归并排序，直接从自底向上进行归并。

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;
import java.util.Comparator;

/**
 * @author gelong
 * @date 2020/6/4 23:34
 */
public class MergeSort2 {

    public static <T> void sort(T[] data, Comparator<T> comparator) {
        sort(data, comparator, data.length);
    }

    private static <T> void sort(T[] data, Comparator<T> comparator, int n) {
        for (int i = 1; i < n; i += i) {
            for (int j = 0; j + i < n; j += 2 * i) {
                if (comparator.compare(data[j + i - 1], data[j + i]) > 0) {
                    // 归并[j, j + i -1] [j + i, j + 2 * i - 1]
                    merge(data, comparator, j, j + i - 1, Math.min(j + 2 * i - 1, n - 1));
                }
            }
        }
    }

    /**
     * 合并[left, mid] [mid + 1, right]
     *
     * @param data       数组
     * @param comparator 比较器
     * @param left       数组1 左边界
     * @param mid        数组1 右边界
     * @param right      数组2 右边界
     * @param <T>        泛型
     */
    private static <T> void merge(T[] data, Comparator<T> comparator, int left, int mid, int right) {
        T[] aux = Arrays.copyOfRange(data, left, right + 1);
        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {
                data[k] = aux[j - left];
                j++;
            } else if (j > right) {
                data[k] = aux[i - left];
                i++;
            } else if (comparator.compare(aux[i - left], aux[j - left]) < 0) {
                data[k] = aux[i - left];
                i++;
            } else {
                data[k] = aux[j - left];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] data = {3, 1, 2, 5, 4};
        sort(data, Integer::compareTo);
        System.out.println(Arrays.toString(data));
    }

}