1

私はマージソートの再帰コードに取り組んでいて、スピードが急上昇しました。私はインターネットと私のアルゴリズム自体を何度も紙に書いてきましたが、問題を理解できないようです。

    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の順序であるテキスト入力ファイルからのものであり、コードは1つおきの番号（3,7と10,1、次に3）のみを並べ替えます。 7,1,10。

私の考えでは、3,9、7,2など、3,9,7,2、10,5,1,8などと並べ替える必要がありますが、そうではありません。ここで私を助けてくれませんか？

4

4 に答える 4

4

私が知る限り、問題のあるコードは次のとおりです。

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

このコードは、の場合に1つの要素配列を返しhigh-low<=1ます。したがって、forlow = 0, high=1メソッドは、並べ替えられた2要素の配列を返すことが期待される場合、0番目の要素を返します。次のように変更できます。

if(low==high) //one element passed
//same here
于 2013-03-26T05:39:48.587 に答える
1

ここでは、次の2つのことを変更する必要があります。

1）前の投稿で指摘したように変更if (middle==low)します。if (high==low)

2）または単にに変更else if (firstHalfSorted[m] **<** secondHalfSorted[n])します。else if (firstHalfSorted[m] **<=** secondHalfSorted[n])else

現在、コードは繰り返し番号をサポートしていないため、2番目のポイントは重要です。言い換えれば、あなたは、両方が等しいif-else場合にケースを考慮しないという意味で網羅的ではありませんでした。firstHalfSorted[m]secondHalfSorted[n]

于 2014-03-16T23:42:58.193 に答える
0

マージソートの場合、データを2つの部分に分割し、それらの2つの部分を繰り返してから、マージするだけで済みます。真ん中ややろうとしていることを見つけてデータを分割しようとするのではなく、リスト全体を2つに分割するだけです。

例えば：

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)。

于 2013-03-26T05:23:09.270 に答える
0

これは、再帰を伴う単純なマージソートコードです。

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

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

于 2017-07-12T14:06:08.123 に答える