递归归并排序Java程序

Question

我一直在编写合并排序递归代码，但遇到了一个障碍。我通过互联网和我的算法本身在纸上看了很多次，我似乎就是弄不明白这个问题。

    public static int[] mergesort(int[] data, int low, int high)
    {
        int middle = (high+low)/2;
        if (middle==low)
        {
            int[] data2 = new int [1];
            data2[0]=data[middle];
            return data2;
        }
        else
        {
            int[] firstHalfSorted = mergesort(data, low, middle);
            int[] secondHalfSorted = mergesort(data, middle+1, high);
            return (merge(firstHalfSorted, secondHalfSorted));
        }
    }

    public static int[] merge(int[] firstHalfSorted, int[] secondHalfSorted)
    {
        int[] SortedArray = new int[firstHalfSorted.length+secondHalfSorted.length];
        int m = 0;
        int n = 0;
        int count = 0;
        while (m<firstHalfSorted.length && n<secondHalfSorted.length)
        {
            if (firstHalfSorted[m]>secondHalfSorted[n])
            {
                SortedArray[count]=secondHalfSorted[n];
                count++;
                n++;
            }
            else if (firstHalfSorted[m]<secondHalfSorted[n])
            {
                SortedArray[count]=firstHalfSorted[m];
                count++;
                m++;
            }
        }
        if (m!=firstHalfSorted.length)
        {
            while(m<firstHalfSorted.length){
                SortedArray[count]=firstHalfSorted[m];
                count++;
                m++;
            }
        }
        if (n!=secondHalfSorted.length)
        {
            while(n<secondHalfSorted.length){
                SortedArray[count]=secondHalfSorted[n];
                count++;
                n++;
            }
        }
        return SortedArray;
    }

这就是代码。问题出在一个包含数字3,9,7,2,10,5,1,8的文本输入文件中，代码只对3,7和10,1，3,7,1,10每隔一个数字进行排序。

根据我所有的想法，它应该排序3,9,7,2，等等，然后，3,9，7,2和10,5,1,8等等，但它没有！你们能帮帮我吗？

Answer 1

据我所知，有问题的代码是：

if (middle==low)
{
    int[] data2 = new int [1];
    data2[0]=data[middle];
    return data2;
}

当为high-low<=1时，此代码将返回一个元素数组。因此，for low = 0, high=1方法将返回第零个元素，而它本应返回已排序的两个元素数组。您可以将其更改为：

if(low==high) //one element passed
//same here

Answer 2

您必须在此处更改以下两项内容：

1)如上一篇文章所述，将if (middle==low)更改为if (high==low)。

2)将else if (firstHalfSorted[m] **<** secondHalfSorted[n])更改为else if (firstHalfSorted[m] **<=** secondHalfSorted[n])或简单的else。

第二点很重要，因为目前您的代码不支持重复的数字。换句话说，您的if-else不是详尽的，因为它们不考虑firstHalfSorted[m]和secondHalfSorted[n]都相等的情况。

Answer 3

对于merge-sort，您只需要将数据分成两部分，在这两部分上递归，然后合并。不要试图通过找到中间部分或任何你想要做的事情来划分你的数据，相反，只要将整个列表分成两半即可。

例如：

private int[] mergesort(int[] data) {
    int[] half1 = new int[data.length / 2];
    int[] half2 = new int[(data.length % 2 == 0)? data.length / 2 : data.length / 2 + 1];
    for (int i = 0; 2 * i < data.length; i++) {
        half2[i] = data[2 * i];
        if (2 * i + 1 < data.length) half1[i] = data[2 * i + 1];
    }
    int[] firstHalfSorted = mergesort(half1);
    int[] secondHalfSorted = mergesort(half2);
    return merge(firstHalfSorted, secondHalfSorted);
}

如果您想保留当前的方法(实际上看起来它应该可以工作)，您只需要通过将if (middle == low)更改为if (high == low)来修复整数除法错误。