合并排序Bug的麻烦

Question

我正试图实现合并排序，我被合并函数卡住了:

下面是我的函数:

public static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int hi) {
    // Copy the elements to the aux array
    for(int i = low; i < a.length; i++) {
        aux[i] = a[i];
    }
    int i = low, j = mid + 1;
    for (int k = low; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

输入如下:

[2, 4, 6, 8, 3, 5, 7, 9]

产生如下结果:

[2, 3, 3, 3, 3, 5, 7, 9]

下面是调用本身:

    int mid = 0 + (my_array.length - 0) / 2;
    MergeSort.merge(my_array, my_array, 0, mid -1, my_array.length-1);

我不能确定。

Answer 1

a和aux是同一个数组。首先，你把数组复制到它本身，这是毫无用处的。然后，在第二个循环中，在读取值时更改值，这会把一切都搞砸。

不传递两个(相同的)数组，而是在merge方法中创建一个新数组并返回它。

Answer 2

看来你实际上不知道这里合并是什么意思。归并排序是一种分而治之算法。这里，征服部分意味着你要归并两个排序数组。因此，要合并它们，您总是将两个数组中最低的项放入输出数组的下一个位置，并在取出该项的数组中向前移动一个位置。

把这个合并方法作为一个基本的例子，只是为了了解这个概念。

public class MergeTest {
public static void main(String[] args) {
    int[] sorted1 = new int[] {2, 5, 6, 8, 10};
    int[] sorted2 = new int[] {1, 3, 4, 7, 9};
    int[] result = merge(sorted1, sorted2);
    // returns [1,2,3,4,5,6,7,8,9,10]
}
public static int[] merge (int[] input1, int[] input2) {
    int[] output = new int[input1.length + input2.length];
    int pos1 = 0;
    int pos2 = 0;
    while (pos1 < input1.length && pos2 < input2.length) {
        int val1 = input1[pos1];
        int val2 = input2[pos2];
        if (val1 < val2) {
            output[pos1++ + pos2] = val1;
        } else {
            output[pos1 + pos2++] = val2;
        }
    }
    while (pos1 < input1.length) {
        int val = input1[pos1];
        output[pos1++ + pos2] = val;
    }
    while (pos2 < input2.length) {
        int val = input2[pos2];
        output[pos1 + pos2++] = val;
    }
    return output;
}
}

这里有一点额外的:mergeSort方法本身。

public static int[] mergeSort (int[] input) {
    if (input.length == 1) {
        return input;
    }
    int middle = input.length / 2;
    // divide
    int[] divided1 = Arrays.copyOfRange(input, 0, middle);
    int[] divided2 = Arrays.copyOfRange(input, middle, input.length);
    // conquer
    int[] sorted1 = mergeSort(divided1);
    int[] sorted2 = mergeSort(divided2);
    return merge(sorted1, sorted2);
}