合并排序算法不起作用

Question

这是我在 java 中的合并排序代码：

public class MergeSort {

    public static void mergesort(int[] input) {

        int inputSize = input.length;
        if(inputSize < 2) {
            return;
        }
        int[] left = new int[inputSize/2];
        int[] right = new int[inputSize/2];
        int count = 0;
        for(int i=0; i < inputSize/2; i++) {
            left[i] = input[i];
        }
        for(int i=inputSize/2; i<inputSize; i++) {
            right[count] = input[i];
            count++;
        }

        mergesort(left);
        mergesort(right);
        merge(left, right, input);

    }

    public static int[] merge(int[] returnArr, int[] left, int[] right) {
        int leftSize = left.length;
        int rightSize = right.length;
        int i = 0;
        int j =0;
        int k = 0;
        int count = 0;
        while(i < leftSize && j < rightSize) {
            if(left[i] <= right[j]) {
                returnArr[k] = left[i];
                i++;
            }
            else {
                returnArr[k] = right[j];
                j++;
            }
            k++;
        }

        while(i<leftSize) {
            returnArr[k] = left[i];
            i++;
            k++;
        }
        while(j < rightSize) {
            returnArr[k] = right[j];
            j++;
            k++;
        }

        for(int x=0; x<returnArr.length; x++) {
            System.out.print(returnArr[x]);
        }

        return returnArr;
    }
    public static void main(String[] args) {
        int[] array = {3,4,6,2,7,1,8,6};
        mergesort(array);

    }

}

我的问题是出现越界异常。我正在使用调试器并发现在 mergesort(left) 和 mergesort(right) 递归完成后运行。

进入merge函数的数组left和right的值分别为[3]和[4]，是正确的。

但是当调试器跳转到合并函数时，左边的值为 [3]，右边的由于某种原因长度为 2 且值为 [3,4]。

这是我越界异常的来源，虽然我不确定为什么当合并函数第一次运行时，它会更改 "right" 的值。

Answer 1

一个显而易见的问题是您不应该创建 2 个大小为 inputSize/2 的数组。制作两个 inputSize/2 和 inputsize-inputSize/2 的数组。否则该算法对于奇数长度数组将失败。

同样以正确的参数顺序调用函数。 merge( input, left, right);

Answer 2

我修复了你的代码并将它们合并为 1 个方法，left.length 和 right.length 受限于 input.length 所以你只需要循环 input.length:

public static void mergeSort(int[] input)
{
    if (input.length < 2)
    {
        return;
    }

    int[] left = new int[input.length / 2];
    int[] right = new int[input.length - input.length / 2];

    for (int i = 0; i < input.length; i++)
    {
        if (i < input.length / 2)
            left[i] = input[i];
        else
            right[i - input.length / 2] = input[i];
    }

    mergeSort(left);
    mergeSort(right);

    for (int i = 0, l = 0, r = 0; i < input.length; i++)
    {
        if (l >= left.length)
        {
            input[i] = right[r];
            r++;
        }
        else if (r >= right.length)
        {
            input[i] = left[l];
            l++;
        }
        else
        {
            if (left[l] >= right[r])
            {
                input[i] = right[r];
                r++;
            }
            else
            {
                input[i] = left[l];
                l++;
            }
        }
    }
}

Answer 3

您的代码有两个问题：

1- 正如@coderredoc 所说：您的左右数组大小错误：

示例：如果您有一个包含 7 个元素的数组，您的左右数组的大小将为 7/2 = 3，因此左右数组中总共有 6 个元素，而不是 7 个。

2- 您在 mergeSort 函数中调用 merge 函数时参数顺序错误：应该是 returnArr, left, right 而不是 left,right, returnArr.

说明：

如果您将左数组作为第一个参数传递，它将合并右数组和左数组中的returnArr。但是您的左数组的大小为 3，而其他数组的大小之和为 7 + 3 = 10，这就是您得到 OutOfBoundsException 的原因。

你需要调用 merge(input,left,right);

这是最终版本：

public class MergeSort {

    public static void mergesort(int[] input) {

        int inputSize = input.length;
        if(inputSize < 2) {
            return;
        }
        int[] left = new int[inputSize/2];
        int[] right = new int[inputSize-inputSize/2];
        int count = 0;
        for(int i=0; i < inputSize/2; i++) {
            left[i] = input[i];
        }
        for(int i=inputSize/2; i<inputSize; i++) {
            right[count] = input[i];
            count++;
        }

        mergesort(left);
        mergesort(right);
        merge(input,left, right);

    }

    public static int[] merge(int[] returnArr, int[] left, int[] right) {
        int leftSize = left.length;
        int rightSize = right.length;
        int i = 0;
        int j =0;
        int k = 0;
        int count = 0;
        while(i < leftSize && j < rightSize) {
            if(left[i] <= right[j]) {
                returnArr[k] = left[i];
                i++;
            }
            else {
                returnArr[k] = right[j];
                j++;
            }
            k++;
        }

        while(i<leftSize) {
            returnArr[k] = left[i];
            i++;
            k++;
        }
        while(j < rightSize) {
            returnArr[k] = right[j];
            j++;
            k++;
        }

        for(int x=0; x<returnArr.length; x++) {
            System.out.print(returnArr[x]);
        }

        return returnArr;
    }
    public static void main(String[] args) {
        int[] array = {3,4,6,2,7,1,8,6};
        mergesort(array);

    }

}

合并排序算法不起作用

Merge sort algorithm not working

java

algorithm

mergesort