2

学校の課題のために、マージソートを実装する必要があります。

このコードを使用してトリックを実行しました：

static int[] MergeSort(int[] C)
    {
        int left = 0;
        int right = C.Length;
        int middle = (left + right) / 2;
        int[] A, B;
        A = new int[middle];
        B = new int[middle];

        if (C.Length == 0 || C.Length == 1)
        {
            return C;
        }
        else
        {
            for (int i = left; i < middle; i++)
            {
                A[i] = C[i];
                B[i] = C[middle + i];
            }

            MergeSort(A);
            MergeSort(B);
            return Merge(A, B, C);
        }
    }

    static int[] Merge(int[] A, int[] B, int[] C)
    {
        int i, j, k;
        i = j = k = 0;
        int n = A.Length;
        int m = B.Length;
        int c = C.Length;
        int middle = C.Length / 2;

        while (i < n && j < m)
        {
            if (A[i] < B[j])
            {
                C[k] = A[i];
                i++;
            }
            else
            {
                C[k] = B[j];
                j++;
            }
            k++;

            if (i == n)
            {
                for (int b = i; b < B.Length; b++)
                {
                    C[middle + b] = B[b];
                }
            }
            else
            {
                for (int a = i; a < A.Length; a++)
                {
                    C[middle + a] = A[a];
                }
            }
        }

        return C;
    }

ただし、多くの異なる行では機能しません。制約に何か問題があるかどうかを既にデバッグして確認しましたが、問題を見つけることができないようです。

前もって感謝します！

4

2 に答える 2

2

最初に見つけたのは、配列を 2 つに分割する方法です。

A = new int[middle];
B = new int[middle];

長さが均一でない場合は、最後のアイテムを除外します。あなたが持っている必要があります：

A = new int[middle];
B = new int[right - middle];

次に、長さが異なる可能性があるため、それらに個別のループを使用します。

for (int i = left; i < middle; i++) {
  A[i - left] = C[i];
}
for (int i = middle; i < right; i++) {
  B[i - middle] = C[i];
}
于 2012-10-07T19:35:30.540 に答える
1

Guffa の回答に加えて、Merge メソッドのコードを次のように編集する必要があります。

    while (i < n && j < m)
    {
        if (A[i] < B[j])
        {
            C[k] = A[i];
            i++;
        }
        else
        {
            C[k] = B[j];
            j++;
        }
        k++;
    }
    if (i == n)
    {
        for (int b = j; b < B.Length; b++)
        {
            C[k++] = B[b];
        }
    }
    else
    {
        for (int a = i; a < A.Length; a++)
        {
            C[k++] = A[a];
        }
    }

ループ ブロックは k++ の直後に終了する必要がありますが、最初の for ループでは i ではなく j で b を初期化する必要があります。また、C 配列の次の要素のインデックスに注意してください。それは k であり、必ずしも中央 + a または b ではありません。

于 2012-10-07T23:02:57.067 に答える