Bagaimana untuk menulis algoritma isihan timbunan menggunakan C#

Cara menggunakan C# untuk menulis algoritma isihan timbunan

Isih Timbunan ialah algoritma isihan berdasarkan timbunan binari yang lengkap, dan kerumitan masanya ialah O(nlogn). Dalam artikel ini, kami akan menulis algoritma isihan timbunan menggunakan C# dan memberikan contoh kod terperinci.

1. Bina timbunan

Dalam algoritma isihan timbunan, anda perlu membina timbunan maks (atau timbunan min). Sifat timbunan maks ialah nilai nod induk adalah lebih besar daripada atau sama dengan nilai nod anaknya, manakala yang sebaliknya berlaku untuk timbunan min.

Untuk membina timbunan maks, kita boleh menggunakan tatasusunan untuk mewakili timbunan. Nod timbunan disusun dalam susunan hierarki. Memandangkan indeks nod i, kita boleh mencari indeks nod induk dan nod anak dengan:

• Indeks nod induk = (i - 1) / 2
• Indeks nod anak kiri = 2 * i + 1
• Nod Anak Kanan indeks = 2 * i + 2

Menggunakan indeks ini, kita boleh bergerak dengan mudah di sekeliling timbunan dan menolak elemen besar (atau kecil) ke bahagian atas timbunan.

Berikut ialah kod sampel untuk melaksanakan timbunan maks menggunakan C#:

public void BuildMaxHeap(int[] arr, int n, int i)
{
    int largest = i; // 初始化最大元素的索引
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点比父节点大，更新最大元素的索引
    if (left < n && arr[left] > arr[largest])
    {
        largest = left;
    }

    // 如果右子节点比父节点大，更新最大元素的索引
    if (right < n && arr[right] > arr[largest])
    {
        largest = right;
    }

    // 如果最大元素的索引不是父节点的索引，交换父节点和最大元素
    if (largest != i)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // 递归地建立最大堆
        BuildMaxHeap(arr, n, largest);
    }
}

2. Isihan timbunan

Selepas membina timbunan maks, kita boleh menggunakan algoritma isihan timbunan untuk mengisih tatasusunan. Idea isihan timbunan adalah untuk terus menukar elemen terbesar ke penghujung tatasusunan dan mengurangkan julat tatasusunan yang hendak diisih. Langkah-langkah khusus adalah seperti berikut:

• Bina timbunan maksimum
• Tukar elemen atas dan elemen terakhir timbunan
• Laraskan semula timbunan
• Ulang langkah di atas sehingga hanya tinggal satu elemen dalam tatasusunan untuk diisih

Berikut ialah isihan timbunan menggunakan kod Contoh C# untuk:

public void HeapSort(int[] arr)
{
    int n = arr.Length;

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        BuildMaxHeap(arr, n, i);
    }

    // 交换堆顶元素和末尾元素，并重建最大堆
    for (int i = n - 1; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        BuildMaxHeap(arr, i, 0);
    }
}

3. Kod ujian

Untuk mengesahkan bahawa algoritma isihan timbunan kami adalah betul, kami boleh menulis beberapa kod ujian yang menyusun tatasusunan yang dijana secara rawak dan mengeluarkan keputusan untuk semakan. Berikut ialah contoh kod ujian isihan timbunan yang ditulis dalam C#:

int[] arr = { 12, 11, 13, 5, 6, 7 };
HeapSort(arr);

Console.WriteLine("排序后的数组：");
foreach (var element in arr)
{
    Console.Write(element + " ");
}

4. Ringkasan

Melalui langkah di atas, kami telah berjaya menulis algoritma isihan timbunan menggunakan C# dan memberikan contoh kod terperinci. Isihan timbunan ialah algoritma pengisihan yang cekap yang memberikan prestasi yang baik dalam kebanyakan kes. Saya harap artikel ini akan membantu anda memahami dan melaksanakan algoritma isihan timbunan!

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma isihan timbunan menggunakan C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!