为什么我在 java 中出现异常合并排序？

Question

我无法理解为什么我得到 Exception.I 每个阶段的检查结果，但仍然找不到错误。

Temp 是一个数组，我想在其中添加要排序的元素。

A是一个数组，包含要排序的元素打包应用程序；

public class MergeSortDemo

{

    public static void  mergesort(int A[],int temp[],int left,int right)

    {

        int mid;

        if(right>left) //why u need to check this  base case always

        {

            //System.out.println(right);

            //System.out.println(left);

            mid=(right+left)/2;

            mergesort(A,temp,left,mid);

            mergesort(A,temp,mid+1,right);

            merge(A,temp,left,mid+1,right);

        }

    }   

    public static void  merge(int A[],int temp[],int left,int mid,int right)

    {

        int i,left_end,size,temp_pos;

        System.out.println(left);

        System.out.println(right);

        left_end=mid-1; 

        System.out.println(left_end);

        temp_pos=left;

        System.out.println(temp_pos);

        size=right-left+1;

        System.out.println(size);

        while((left<=left_end)&&(mid<=right))

        {

            System.out.println(A[left]);

            System.out.println(A[right]);

            System.out.println(A[mid]);

            if(A[left]<=A[mid])

            {

                temp[temp_pos]=A[left];

                System.out.println(A[left]);

                System.out.println("left in temp");


                temp_pos=temp_pos+1;

                left=left+1;

            }

            else

            {

                System.out.println(A[right]);

                System.out.println("right in temp");

                temp[temp_pos]=A[mid];

                temp_pos=temp_pos+1;

                mid=mid+1;

            }

        }

        while(left<=left_end)

        {

            temp[temp_pos]=A[left];

            System.out.println(A[left]);

            System.out.println("left left");

            left=left+1;

            temp_pos=temp_pos+1;

        }

        while(mid<=right)

        {

            temp[temp_pos]=A[mid];

            System.out.println(A[mid]);

            System.out.println("right left");

            mid=mid+1;

            temp_pos=temp_pos+1;

        }

        for(i=0;i<size;i++)

        {

            A[right]=temp[right];

            //System.out.println(A[right]);

            right=right-1;

        }

        for(i=0;i<size;i++)

        {

            System.out.println(A[i]);

        }

    }

public static void main(String s[])

{

    int ar[]={6,3,2,5,4};

    int p[]=new int[ar.length];

    mergesort(ar,p,0,ar.length-1);

}

}

OutPut 这里显示的是

堆栈跟踪

Exception in thread "main" right in temp

java.lang.ArrayIndexOutOfBoundsException: -1  //why 
     app.MergeSortDemo.merge(MergeSortDemo.java:81)
     app.MergeSortDemo.mergesort(MergeSortDemo.java:19)
     app.MergeSortDemo.mergesort(MergeSortDemo.java:17)
     app.MergeSortDemo.mergesort(MergeSortDemo.java:17)
     app.MergeSortDemo.main(MergeSortDemo.java:91)

Answer 1

你的 merge 方法中的这个循环看起来不对：

        for(i=0;i<=size;i++)
        {
            A[right]=temp[right];
            right=right-1;
        }

例如，假设您使用 left=0,mid=1,right=1.

调用合并

所以size = right-left+1=2

此循环将有 3 次迭代，right 将在最后一次迭代中达到 -1，从而导致您的异常。

正确的循环可能是：

        for(i=0;i<size;i++)
        {
            A[right]=temp[right];
            right=right-1;
        }

编辑：我刚刚对其进行了测试，这确实是问题所在。将 i<=size 更改为 i<size 后，您的代码会生成正确的排序数组：

 [2, 3, 4, 5, 6]

为什么我在 java 中出现异常合并排序？

why i am getting exception mergesort in java?

java

mergesort