Bagaimana untuk melaksanakan algoritma pengisihan gabungan dalam C#

Cara melaksanakan algoritma isihan gabungan dalam C#

Isih Gabung ialah algoritma isihan klasik berdasarkan idea bahagi dan takluk, yang berfungsi dengan membahagikan Masalah besar dibahagikan kepada beberapa masalah kecil, dan kemudian masalah kecil diselesaikan langkah demi langkah dan hasilnya digabungkan untuk menyelesaikan pengisihan. Berikut akan memperkenalkan cara melaksanakan algoritma isihan gabungan dalam C# dan memberikan contoh kod khusus.

Idea asas isihan gabungan adalah untuk membahagikan urutan untuk diisih kepada berbilang jujukan, mengisihnya secara berasingan, dan kemudian menggabungkan urutan yang diisih ke dalam urutan tertib. Kunci kepada algoritma ini adalah untuk melaksanakan operasi pemisahan dan penggabungan bagi urutan.

Pertama, kita perlu menulis fungsi rekursif untuk melaksanakan operasi pisah, membahagikan jujukan asal kepada dua jujukan dan secara rekursif memanggil algoritma isihan gabungan untuk mengisih jujukan. Kod khusus adalah seperti berikut:

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

Seterusnya, kita perlu menulis fungsi cantum untuk menggabungkan dua urutan tertib menjadi satu urutan tertib. Kunci kepada operasi gabungan adalah untuk membandingkan unsur-unsur dalam dua urutan dan meletakkannya ke dalam tatasusunan tambahan mengikut saiz. Kod khusus adalah seperti berikut:

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

Akhirnya, kita boleh mengisih tatasusunan dengan memanggil fungsi MergeSort Kod khusus adalah seperti berikut:

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

Di atas. ialah cara melaksanakan pengisihan gabungan dalam C# Langkah terperinci dan contoh kod algoritma. Dengan membahagi jujukan secara rekursif, mengisih jujukan, dan menggabungkan hasil, kami boleh mengisih jujukan dalam sebarang saiz dengan cekap. Kerumitan masa pengisihan gabungan ialah O(nlogn), yang merupakan algoritma pengisihan yang agak pantas.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pengisihan gabungan dalam C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!