java - 合并排序返回一个包含“0”的大小为 1 的数组，而不是一个已排序的数组

Question

我试图解决这个问题，但到目前为止都失败了。这是我第一次出于学术目的处理排序算法，所以我可能在某个地方犯了一个简单的错误；我一直无法弄清楚。

    private int[] mergeAndDivide(int[] array) {
        if (array.length < 2)
            return array;
        int[] arrayOne = Arrays.copyOfRange(array, 0, (array.length - 1) / 2);
        int[] arrayTwo = Arrays.copyOfRange(array, ((array.length - 1) / 2 + 1), (array.length - 1));
        arrayOne = mergeAndDivide(arrayOne);
        arrayTwo = mergeAndDivide(arrayTwo);
        return merge(arrayOne, arrayTwo);
    }

    private int[] merge(int[] arrayOne, int[] arrayTwo) {
        int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
        int i = 0;
        while (i <= arrayOne.length - 1 && i <= arrayTwo.length - 1) {
            if (arrayOne[i] > arrayTwo[i])
                arrayMerged[i] = arrayTwo[i];
            else
                arrayMerged[i] = arrayOne[i];
        }
        int x = i;
        while (i <= arrayOne.length - 1) {
            arrayMerged[i + arrayTwo.length - 1] = arrayOne[i];
            i++;
        }
        i = x;
        while (i <= arrayTwo.length - 1) {
            arrayMerged[i + arrayOne.length - 1] = arrayTwo[i];
            i++;
        }
        return arrayMerged;
    }

标签： javaarrayssortingmergesort

Answer 1

的第二个参数Arrays.copyOfRange()是切片结束后第一个元素的索引。使用array.length / 2它并使用与第二个切片的起始索引相同的值。

同样，<在合并方法中使用和不调整长度。还有另一个错误：您对 和 使用相同的索引i，您arrayOne应该对每个参数数组和合并数组使用不同的索引。arrayTwoarrayMerged

这是修改后的版本：

    private int[] mergeAndDivide(int[] array) {
        if (array.length < 2)
            return array;
        int[] arrayOne = Arrays.copyOfRange(array, 0, array.length / 2);
        int[] arrayTwo = Arrays.copyOfRange(array, array.length / 2, array.length);
        arrayOne = mergeAndDivide(arrayOne);
        arrayTwo = mergeAndDivide(arrayTwo);
        return merge(arrayOne, arrayTwo);
    }

    private int[] merge(int[] arrayOne, int[] arrayTwo) {
        int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
        int i = 0, j = 0, k = 0;
        while (i < arrayOne.length && j < arrayTwo.length) {
            if (arrayOne[i] <= arrayTwo[j])
                arrayMerged[k++] = arrayOne[i++];
            else
                arrayMerged[k++] = arrayTwo[j++];
        }
        while (i < arrayOne.length) {
            arrayMerged[k++] = arrayOne[i++];
        }
        while (j < arrayTwo.length) {
            arrayMerged[k++] = arrayTwo[j++];
        }
        return arrayMerged;
    }