java 递归归并排序Java程序

Recursive Merge Sort Java Program

提问by Marc Hosang

I've been working on a merge sort recursive code and I've hit a speed bump. I've gone through the internet and my algorithm itself on paper MANY times and I just can't seem to figure out the problem.

我一直在研究合并排序递归代码，但遇到了一个减速带。我已经在纸上浏览了互联网和我的算法本身很多次，但我似乎无法弄清楚问题所在。

    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;
    }

There's the code. The problem is from a text input file with numbers, 3,9,7,2,10,5,1,8 in that order, the code only sorts every other number, being 3,7 and 10,1, then 3,7,1,10.

有代码。问题来自一个包含数字的文本输入文件，按该顺序为 3,9,7,2,10,5,1,8，代码仅对每隔一个数字进行排序，即 3,7 和 10,1，然后是 3， 7、1、10。

By all my thinking it should sort 3,9 then 7,2 and so on then, 3,9,7,2 and 10,5,1,8 and so on and so on, but it does not! Can you guys help me out here?

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

回答by default locale

As far as I can tell, the problematic code is:

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

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

This code will return one element array when high-low<=1. So, for low = 0, high=1method will return zeroth element when it expected to return sorted two-element array. You can change it to:

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

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

回答by UD_CSE_IITB

You have to change the following two things here:

您必须在这里更改以下两件事：

1) Change if (middle==low)to if (high==low)as pointed in the previous post.

1）改变if (middle==low)到if (high==low)如指出在过去后。

2) Change else if (firstHalfSorted[m] **<** secondHalfSorted[n])to else if (firstHalfSorted[m] **<=** secondHalfSorted[n])or simply else.

2)else if (firstHalfSorted[m] **<** secondHalfSorted[n])改为else if (firstHalfSorted[m] **<=** secondHalfSorted[n])或else。

The second point is important because currently your code does not support repeated numbers. In other words, your if-elsewere not exhaustive in the sense that they don't consider the case when both firstHalfSorted[m]and secondHalfSorted[n]are equal.

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

回答by Jimmy Lee

For merge-sort, you need only to divide your data into two parts, recurse on those two parts, and then merge. Instead of trying to divide your data by finding the middle or whatever it is you are trying to do, instead just separate the whole list into two halves.

对于归并排序，您只需要将数据分成两部分，对这两部分进行递归，然后进行合并。不要试图通过找到中间值或任何你想要做的事情来划分你的数据，而是将整个列表分成两半。

For example:

例如：

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 you want to keep your current method (which actually looks like it should work), you just need to fix the integer-division bug by changing if (middle == low)to if (high == low).

如果您想保留当前的方法（实际上看起来应该可以工作），您只需要通过更改if (middle == low)为if (high == low).

回答by Abhishek Dhiman

this is a simple merge sort code with recursion.

这是一个带有递归的简单合并排序代码。

public class solution {

 public static void merge(int[] input, int s, int e){

    int m = (s + e) / 2;

    int temp[] = new int[e - s + 1];

    int s1 = s;
    int s2 = m + 1;

    int i = s1;
    int j = s2;
    int p = 0;
    while(i <= m  && j <= e){
        if(input[i] > input[j]){
            temp[p] = input[j];
            j++;
            p++;
        }else{
            temp[p] = input[i];
            i++;
            p++;
        }
    }//end of while loop

    while(i <= m){
            temp[p] = input[i];
            p++;
            i++;
    }
    while(j <= e){
            temp[p] = input[j];
            p++;
            j++;
    }

    for(int k = 0; k < temp.length; k++){
        input[s + k] = temp[k];
    }
}

public static void callsort(int[] input, int s, int e){

    if(s >= e){
        return ;
    }

    int m = (s + e) / 2;

    callsort(input, s, m);
    callsort(input, m + 1, e);
    merge(input, s, e);

}

public static void mergeSort(int[] input){
    callsort(input , 0 , input.length - 1); 
}
}

Input: 5 6 3 2 1 4 output: 1 2 3 4 5 6

输入：5 6 3 2 1 4 输出：1 2 3 4 5 6