0

Javaとアルゴリズムを同時に学んでいます。このクラスにマージソートを実装しました。

public class Sorter {
    private void merge(int [] numbers, int low, int mid, int high) {
            // create a new array that will contain the merged integers
            int[] arrIntMerged = new int[high - low + 1];

            // set indices
            int i = low, j = mid + 1, k = 0;

            // add the lesser integer into merged array
            while (i <= mid && j <= high) {
                if (numbers[i] < numbers[j]) {
                    arrIntMerged[k] = numbers[i];
                    i++;
                } else {
                    arrIntMerged[k] = numbers[j];
                    j++;
                }
                k++;
            }

            // add anything left in the left side of the array
            while (i <= mid) {
                arrIntMerged[k] = numbers[i];
                i++;
                k++;
            }

            // add anything left in the right side of the array
            while (j <= high) {
                arrIntMerged[k] = numbers[j];
                j++;
                k++;
            }

            // write this newly created array into the positions in the original array
            for (int l = 0; l < arrIntMerged.length; l++) {
                numbers[l + low] = arrIntMerged[l];
            }
        }

        // recursive implementation
        private void _mergeSort(int[] numbers, int low, int high) {
            if (low == high)
                return;
            else {
                // find midpoint while preventing overflow
                int mid = low + (high - low) / 2;
                // sort left and right side
                _mergeSort(numbers, low, mid);
                _mergeSort(numbers, mid + 1, high);
                // merge both sides
                merge(numbers, low, mid + 1, high);
            }
        }

        // friendly interface to begin merge sort
        public void mergeSort(int[] numbers) {
            _mergeSort(numbers, 0, numbers.length - 1);
        }
}

次に、このコードを Eclipse のスクラップブックで調べました。

Sorter sorter = new Sorter();
int[] nums = {5, 6, 7, 8, 1, 2, 3, 4};
sorter.mergeSort(nums);
System.out.println(Arrays.toString(nums));

残念ながら、標準出力は を読み取ります[2, 3, 4, 5, 6, 7, 8, 1]が、これは順不同です。マージソートが間違っているのはなぜですか? の境界条件についてはかなり確信がある_mergeSortので、merge関数が間違っているのではないかと思います。

4

1 に答える 1

1

あなたの問題は、 の次の割り当てに由来しますmerge。

j = mid + 1

midは既にマージの右側の最初の番号へのインデックスです。この増分により、マージ ロジックの残りの部分が間違った配列位置から開始されます。

midあなたが学習しているように見えるので、必要な実際のコード変更を投稿してあなたの経験を台無しにすることはしませんが、ここでヒント: 物事を値と比較するすべての場所を確認してください。

于 2012-05-14T20:14:20.583 に答える