0

再帰ステップごとに3つの配列を作成すると、スペースがかかりすぎるのではないかと心配していますが、別の方法を見つけることができませんでした。何が悪いのか教えてください。

public static int[] split(int [] vector){

    if(vector.length <= 1 || vector == null) 
        return vector;
    int len = vector.length;

    int[] list1 = new int[len / 2];
    // If the number of elements is odd the second list will be bigger
    int[] list2 = new int[len / 2 + (len % 2)];

    // Here we assign the elements to 2 separate lists
    for(int x = 0; x < len / 2; x++)
        list1[x] = vector[x];
    for(int j = 0, i = len / 2; j < list2.length; i++, j++)
        list2[j]=vector[i];

    // Apply the recursion, this will eventually order the lists
    list1 = split(list1);
    list2 = split(list2);

    // Here we take the 2 ordered lists and merge them into 1
    int i = 0, a = 0, b = 0;
    int[] listfinal = new int[len];
    while(i < len){
        if(a >= list1.length){
            listfinal[i] = list2[b]; 
            b++;
        } else if(b >= list2.length){
            listfinal[i] = list1[a]; 
            a++;
        } else if(list1[a] <= list2[b]){
            listfinal[i] = list1[a]; 
            a++;
        } else if(list1[a] > list2[b]){
            listfinal[i] = list2[b]; 
            b++;
        }
        i++;
    }
    return listfinal; // Return the merged and ordered list
}
4

2 に答える 2

1

マージソートを実行するために複数の一時配列を作成する必要はありません。間違っているのは、配列をコピーして再帰呼び出しに渡すことです。代わりに、元の配列を渡す必要があります。

JDKでのマージソートの実装を確認することは有益かもしれません-Arrays.javaの1146行目を参照してください。

于 2012-11-25T18:04:59.083 に答える
0

これは、トップレベルの入力サイズに等しい単一の配列を割り当て、それをすべての再帰に再利用するコードです。百万の整数では、これは私のマシンでは約300ミリ秒かかり、Javaライブラリソートは230ミリ秒かかります。チューニングの努力は必要ありません、私は推測します...

// Sort the elements of a between lo and hi inclusive.
private static void sortImpl(int [] a, int lo, int hi, int [] tmp) {

    if (hi <= lo) return;

    // Recur on sublists.
    int mid = (hi + lo) / 2;
    sortImpl(a, lo, mid, tmp);
    sortImpl(a, mid + 1, hi, tmp);

    // Move past items already in the right place.
    int t1 = lo;
    while (a[t1] < a[mid + 1]) t1++;

    // Merge sublists into result.
    int p1 = t1;
    int p2 = mid + 1;
    int i = t1;
    System.arraycopy(a, t1, tmp, t1, mid - t1 + 1);
    while (p1 <= mid)
        a[i++] = (p2 > hi || tmp[p1] < a[p2]) ? tmp[p1++] : a[p2++];
}

public static void sort(int [] a) {
    sortImpl(a, 0, a.length - 1, new int[a.length]);
}
于 2012-11-25T19:28:51.760 に答える