合并排序会返回包含“ 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;
    }

Answer 1

您的代码逻辑似乎不是合并排序。这是正确的合并排序代码：

public static void main(String[] args) {

    int arr[] = {12, 11, 13, 5, 6, 7};

    System.out.println("\nSorted array");
    for(int i=0;i<=arr.length-1;i++){
        System.out.println("Initial Arr element:"+arr[i]);
    }

    mergeS(arr, 0, arr.length-1);

    System.out.println("\nSorted array");
    for(int i=0;i<=arr.length-1;i++){
        System.out.println("Sorted Arr element:"+arr[i]);
    }
}


public static void mergeS(int[] arr,int startI,int endI){
    //System.out.println("StartIndex:"+startI+" EndIndex:"+endI)

    if (startI< endI)
    {
        // Find the middle point
        int m = (startI+endI)/2;

        // Sort first and second halves
        mergeS(arr,startI, m);
        mergeS(arr , m+1, endI);

        // Merge the sorted halves
        merge(arr, startI,m, endI);
    }
}


public static void merge(int arr[], int startI, int midpoint, int endI){
    // Find sizes of two subarrays to be merged
    int n1 = midpoint - startI + 1;
    int n2 = endI - midpoint;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[startI + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[midpoint + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = startI;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

}

Answer 2

在除法例程中，Arrays.copyOfRange to参数是排他的，这意味着它不会在结果中包括to索引。同样，在合并例程中，您必须使用2个变量来迭代2个数组，并且在大多数情况下，我将<=更改为

import java.util.Arrays;

class Solution {
    private static int[] mergeAndDivide(int[] array) {
        if (array.length < 2) return array;
        int[] arrayOne = Arrays.copyOfRange(array, 0, ((array.length - 1) / 2) + 1); // the final index is exclusive meaning it will not be included in the bisected array
        int[] arrayTwo = Arrays.copyOfRange(array, ((array.length - 1) / 2 + 1), array.length);
        arrayOne = mergeAndDivide(arrayOne);
        arrayTwo = mergeAndDivide(arrayTwo);
        return merge(arrayOne, arrayTwo);
    }

    private static int[] merge(int[] arrayOne, int[] arrayTwo) {
        int[] arrayMerged = new int[arrayOne.length + arrayTwo.length];
        int i = 0;
        int j = 0;
        while (i < arrayOne.length && j < arrayTwo.length) { // you need 2 variables to index first and second array;
            if (arrayOne[i] > arrayTwo[j]) {
                arrayMerged[i + j] = arrayTwo[j];
                j++;
            } else {
                arrayMerged[i + j] = arrayOne[i];
                i++;
            }
        }

        while (i < arrayOne.length) {
            arrayMerged[i + j] = arrayOne[i];
            i++;
        }
        while (j < arrayTwo.length) {
            arrayMerged[i + j] = arrayTwo[j];
            j++;
        }
        return arrayMerged;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeAndDivide(new int[]{3, 4, 5, 6, 1})));
    }
}


Result : [1, 3, 4, 5, 6]

Answer 3

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

类似地，请使用<，并且不要在合并方法中调整长度。还有另一个错误：在i，arrayOne和arrayTwo中使用相同的索引arrayMerged，在每个参数数组和合并数组中应使用不同的索引。

这里是修改后的版本：

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