java - 我的合并排序的实现不起作用

Question

合并排序算法的此实现失败，因为 ArrayIndexIs 越界。

public static int[] mergeSort(int[] toBeSorted) {
    //If there is only one item in the array, and it is said to be sorted
    if (toBeSorted.length <= 1){
        return toBeSorted;
    }

    //find the indexes of the two sub-groups
    int[] left = new int[toBeSorted.length/2];
    int[] right = new int[toBeSorted.length-left.length];
    //Fill each sub-group with the correct numbers
    //Starting with the left group
    for(int i = 0; i <= left.length - 1; i++){
        left[i] = toBeSorted[i];
    }
    //Then the right group
    for(int i = left.length - 1; i <= toBeSorted.length - 1; i++){
        right[i] = toBeSorted[i];
    }


    //Merge sort each sub-group
    mergeSort(left);
    mergeSort(right);

    //Merge the two sub-groups
    toBeSorted = merge(left, right);

    return toBeSorted;
}

//Merging method
public static int[] merge(int[] left, int[] right){
    //Answer array
    int[] merged = new int[left.length + right.length];
    //Next index to check in each array
    int lCursor = 0;
    int rCursor = 0;
    //Next index to place numbers into answer
    int mergedCursor = 0; 

    //The merging part:
    //If there are still items to merge, then do so
    while(mergedCursor != merged.length){
        //left index is empty
        if(lCursor == left.length) {
            merged[mergedCursor] = right[rCursor];
            //increment the correct cursors
            rCursor += 1;
            mergedCursor += 1;
        }
        //right index is empty
        else if(rCursor == right.length) {
            merged[mergedCursor] = right[lCursor];
            //increment the correct cursors
            lCursor += 1;
            mergedCursor += 1;
        } 
        //Left side is smaller
        else if(left[lCursor]<right[rCursor]){
            merged[mergedCursor] = left[lCursor];
            //increment the correct cursors
            lCursor += 1;
            mergedCursor +=1;
        }
        //Right side is smaller
        else if(right[rCursor]<left[lCursor]){
            merged[mergedCursor] = right[rCursor];
            //increment the correct cursors
            rCursor += 1;
            mergedCursor +=1;
        }
    }
    //return the merged output
    return merged;
}

for 循环内将数字分配给正确数组的行是问题所在，但我不知道为什么。另外，最初我在 for 循环中有 i = left.length，但这导致整个右数组被设置为零。

编辑:我将第二个 for 循环更改为:

  for(int i = 0; i <= right.length - 1; i++){
        right[i] = toBeSorted[i + left.length];
    }

现在正确的数组已被正确填充。

编辑2:我修复了合并部分。由于某些奇怪的原因，当发现索引为空时，我仍然从空数组中获取。我还将其更改为增强的 for 循环以摆脱 mergedCursor。新的合并方法如下:

    public static int[] merge(int[] left, int[] right){
    //Answer array
    int[] merged = new int[left.length + right.length];
    //Next index to check in each array
    int lCursor = 0;
    int rCursor = 0;


    //The merging part:
    //Keep going until output array is full
    for (int i = 0; i <= merged.length - 1; i++) {
        //left index is empty
        if(lCursor == left.length) {
            merged[i] = right[rCursor];
            //increment the correct cursor
            rCursor += 1;
        }
        //right index is empty
        else if(rCursor == right.length) {
            merged[i] = left[lCursor];
            //increment the correct cursor
            lCursor += 1;
        } 
        //Left side is smaller
        else if(left[lCursor]<right[rCursor]){
            merged[i] = left[lCursor];
            //increment the correct cursor
            lCursor += 1;
        }
        //Right side is smaller
        else if(right[rCursor]<left[lCursor]){
            merged[i] = right[rCursor];
            //increment the correct cursor
            rCursor += 1;
        }
    }
    //return the merged output
    return merged;
}

Answer 1

在第二个 for 循环中，您从 (i) 开始 (left.Length - 1)。你想要的是

for (int i = right.Length, j = 0; (j <= right.Length - 1) && (i <= toBeSorted.Length - 1); i++, j++)
{
    right[j] = toBeSorted[i];
}

此外，结束第一个循环的值 (left.Length - 1) 与开始下一个循环的值相同。这意味着您将获得两个(左和右)数组中的中间值。但这可能不是您想要的。所以我将其更改为 (right.Length) 而不是 (right.Length - 1)。