18.3.归并排序

发表于 更新于 分类于 ， 阅读次数： 5 本文字数： 155 阅读时长 ≈ 1 分钟

18.3.Merge Sort

1.The step of Merge Sort

  • Split items into 2 roughly even pieces.
  • Mergesort each half (steps not shown, this is a recursive algorithm!)
  • Merge the two sorted halves to form the final result.

2.Step implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static double merge(double[] a, double[] b) {
    double[] c = new double[a.length + b.length];
    int i = 0; j = 0;
    for (int k = 0; k < c.length; k += 1) {
        if (k >= a.length) c[k] = b[j++];
        if (k >= b.length) c[k] = a[i++];
        if (a[i] <= b[j]) c[k] = a[i++];
        else c[k] = b[j++]; 
    }

    return c;
}

public static double[] mergeSort(double[] input) {
    int N = input.length;
    if (N <= 1) return input;
    double[] a = double[N / 2];
    double[] b = double[N - N / 2];
    for (int i = 0; i < a.length; i += 1) a[i] = input[i];
    for (int j = 0; j < b.length; j += 1) b[j] = input[j + N / 2];
    return merge(mergeSort(a), mergeSort(b));
}