So schreiben Sie einen Heap-Sortieralgorithmus mit C#

So schreiben Sie mit C# einen Heap-Sortieralgorithmus

Heap Sort ist ein Sortieralgorithmus, der auf einem vollständigen binären Heap basiert und dessen zeitliche Komplexität O(nlogn) beträgt. In diesem Artikel schreiben wir den Heap-Sortieralgorithmus mit C# und stellen detaillierte Codebeispiele bereit.

1. Erstellen Sie einen Heap

Im Heap-Sortieralgorithmus müssen Sie zunächst einen Max-Heap (oder Min-Heap) erstellen. Die Eigenschaft des Max-Heaps besteht darin, dass der Wert des übergeordneten Knotens größer oder gleich dem Wert seines untergeordneten Knotens ist, während für den Min-Heap das Gegenteil gilt.

Um einen maximalen Heap zu erstellen, können wir ein Array verwenden, um den Heap darzustellen. Die Knoten des Heaps sind hierarchisch angeordnet. Bei einem gegebenen Knotenindex i können wir die Indizes seiner übergeordneten und untergeordneten Knoten wie folgt ermitteln:

• Index des übergeordneten Knotens = (i - 1) / 2
• Index des linken untergeordneten Knotens = 2 * i + 1
• Rechter untergeordneter Knoten index = 2 * i + 2

Mit diesen Indizes können wir uns leicht im Heap bewegen und große (oder kleine) Elemente an die Spitze des Heaps schieben.

Hier ist ein Beispielcode zum Implementieren des maximalen Heaps mit 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. Heap-Sortierung

Nachdem wir den maximalen Heap erstellt haben, können wir den Heap-Sortieralgorithmus verwenden, um das Array zu sortieren. Die Idee der Heap-Sortierung besteht darin, das größte Element kontinuierlich am Ende des Arrays auszutauschen und den zu sortierenden Bereich des Arrays zu verringern. Die spezifischen Schritte sind wie folgt:

• Erstellen Sie den maximalen Heap.
• Tauschen Sie das oberste Element und das letzte Element des Heaps.
• Passen Sie den Heap neu an.
• Wiederholen Sie die obigen Schritte, bis nur noch ein Element im Array vorhanden ist sortiert werden

Das Folgende ist eine Heap-Sortierung mit C#-Beispielcode für:

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. Testcode

Um zu überprüfen, ob unser Heap-Sortieralgorithmus korrekt ist, können wir einen Testcode schreiben, der ein zufällig generiertes Array sortiert und gibt die Ergebnisse zur Überprüfung aus. Das Folgende ist ein Beispiel für einen in C# geschriebenen Heap-Sortier-Testcode:

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

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

4. Zusammenfassung

Durch die oben genannten Schritte haben wir erfolgreich einen Heap-Sortieralgorithmus mit C# geschrieben und detaillierte Codebeispiele bereitgestellt. Heap-Sortierung ist ein effizienter Sortieralgorithmus, der in den meisten Fällen eine gute Leistung bietet. Ich hoffe, dieser Artikel hilft Ihnen, den Heap-Sortieralgorithmus zu verstehen und zu implementieren!

Das obige ist der detaillierte Inhalt vonSo schreiben Sie einen Heap-Sortieralgorithmus mit C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!