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は同じ配列です。したがって、最初に配列をそれ自体にコピーしますが、これはまったく役に立ちません。次に、2 番目のループで、読み取り中に値を変更すると、すべてが台無しになります。

2 つの (同一の) 配列を渡す代わりに、merge メソッドで新しい配列を作成して返します。

于 2013-04-10T15:31:05.233 に答える
1

ここでのマージが何を意味するのか、実際にはわかっていないようです。マージソートは、分割統治アルゴリズムです。ここで、征服部分は、2 つのソートされた配列をマージしようとしていることを意味します。したがって、それらをマージするには、常に 2 つの配列の最下位の項目を取得し、それを出力配列の次の位置に配置し、項目を取得した配列内の位置を 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 に答える