使用 java 的合并排序 recusrion 错误问题

Question

我正在关注使用 java 的合并排序算法的 YouTube 视频教程。

但是我一直收到这个错误:

Exception in thread "main" java.lang.WhosebugError 
        at merge_sort.msort(merge_sort.java:27)

我的代码：

public static int[] msort(int a[])
    {
        int n = a.length;
        int m = n / 2;
        int l[] = new int[m];
        int r[];
        if(n % 2 == 0) 
        {
            r = new int[m];
        }
        else
        {
            r = new int[m+1];
        }
        for(int i = 0; i < m; i++)
        {
            l[i] = a[i];
        }
        for(int j = 0; j < r.length; j++)
        {  
           r[j] = a[m+j];
        }
        int res[] = new int[n];
        l = msort(l);
        r = msort(r);
        res = merge(l, r);
        return res;
    }
    public static int[] merge(int l[], int r[])
    {
        int len = l.length + r.length;
        int res[] = new int[len];
        int lp = 0, rp = 0, resp = 0;
        while(lp < l.length || rp < r.length)
        {
            if(lp < l.length && rp < r.length)
            {
                if(l[lp] < r[rp])
                {
                    res[resp++] = l[lp++];
                }
                else
                {
                    res[resp++] = r[rp++];
                }
            }
            else if(lp < l.length)
            {
                res[rp++] = l[lp++]; 
            }
            else if(rp < r.length)
            {
                res[rp++] = r[rp++]; 
            }
        }
        return res;
    }

谁能帮我解决这个问题？谢谢

Answer 1

首先，您缺少停止条件。如果待排序数组的长度<2，应该停止递归：

public static int[] msort(int a[])
{
    if (a.length < 2) { // add this condition
        return a;
    }

    ...
}

其次，您在两个数组索引中有错别字：

        else if(lp < l.length)
        {
            res[rp++] = l[lp++]; 
        }
        else if(rp < r.length)
        {
            res[rp++] = r[rp++]; 
        }

应该是

        else if(lp < l.length)
        {
            res[resp++] = l[lp++]; 
        }
        else if(rp < r.length)
        {
            res[resp++] = r[rp++]; 
        }

使用 java 的合并排序 recusrion 错误问题

Issue with merge sort recusrion error using java

java

mergesort