C# でマージ ソート アルゴリズムを実装する方法

#C でマージ ソート アルゴリズムを実装する方法

#マージ ソートは、大きな問題を複数の小さな問題に分割する分割統治の考え方に基づいた古典的な並べ替えアルゴリズムです。問題を解決し、小さな問題を徐々に解決し、その結果を統合してランキングを完成させます。以下では、C# でマージ ソート アルゴリズムを実装する方法と具体的なコード例を紹介します。

マージ ソートの基本的な考え方は、ソート対象のシーケンスを複数のサブシーケンスに分割し、個別にソートしてから、ソートされたサブシーケンスを順序付けられたシーケンスにマージすることです。このアルゴリズムの鍵は、サブシーケンスの分割および結合操作を実装することです。

まず、分割操作を実装する再帰関数を作成し、元のシーケンスを 2 つのサブシーケンスに分割し、マージ ソート アルゴリズムを再帰的に呼び出してサブシーケンスを並べ替える必要があります。具体的なコードは次のとおりです。

static void MergeSort(int[] array, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        MergeSort(array, left, middle);
        MergeSort(array, middle + 1, right);
        Merge(array, left, middle, right);
    }
}

次に、2 つの順序付きサブシーケンスを 1 つの順序付きシーケンスにマージするマージ関数を作成する必要があります。マージ操作の鍵は、2 つのサブシーケンス内の要素を比較し、それらをサイズ順に補助配列に入れることです。具体的なコードは次のとおりです:

static void Merge(int[] array, int left, int middle, int right)
{
    int[] temp = new int[array.Length];
    int i = left;
    int j = middle + 1;
    int k = left;

    while (i <= middle && j <= right)
    {
        if (array[i] <= array[j])
        {
            temp[k] = array[i];
            i++;
        }
        else
        {
            temp[k] = array[j];
            j++;
        }
        k++;
    }

    while (i <= middle)
    {
        temp[k] = array[i];
        i++;
        k++;
    }

    while (j <= right)
    {
        temp[k] = array[j];
        j++;
        k++;
    }

    for (int l = left; l <= right; l++)
    {
        array[l] = temp[l];
    }
}

最後に、MergeSort 関数を呼び出して、並べ替える配列を並べ替えることができます。具体的なコードは次のとおりです:

static void Main(string[] args)
{
    int[] array = { 5, 3, 8, 4, 2, 1, 9, 7, 6 };
    MergeSort(array, 0, array.Length - 1);

    Console.WriteLine("排序后的数组：");
    for (int i = 0; i < array.Length; i++)
    {
        Console.Write(array[i] + " ");
    }

    Console.ReadLine();
}

上記は詳細な手順ですC# でのマージ ソート アルゴリズムの実装とコード例。シーケンスを再帰的に分割し、サブシーケンスを並べ替え、結果をマージすることで、任意のサイズのシーケンスを効率的に並べ替えることができます。マージ ソートの時間計算量は O(nlogn) であり、比較的高速なソート アルゴリズムです。

以上がC# でマージ ソート アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。