0

我正在尝试实现合并排序，但遇到了合并功能：

这是我的功能：

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);

我不能完全确定。

4

2 回答 2

1

a并且aux是同一个数组。因此，您首先将数组复制到自身中，这毫无用处。然后，在第二个循环中，您在读取值时更改它，这会搞砸一切。

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

于 2013-04-10T15:31:05.233 回答
1

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

以这种合并方法为例，只是为了理解。

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);
}
于 2013-04-10T16:06:06.607 回答