Heim  >  Artikel  >  Backend-Entwicklung  >  C#-Heap-Sortierung

C#-Heap-Sortierung

黄舟
黄舟Original
2017-02-09 16:20:371149Durchsuche

C#-Heap-Sortierung

using System;  
using System.Collections;  
namespace Sort  
{  
    public class HeapSorter  
    {  
        public static int[] Sort(int[] sortArray)  
        {  
            BuildMaxHeap(sortArray);  
            for (int i = (sortArray.Length - 1); i > 0; i--)  
            {  
                Swap(ref sortArray[0], ref sortArray[i]); // 将堆顶元素和无序区的最后一个元素交换  
                MaxHeapify(sortArray, 0, i); // 将新的无序区调整为堆,无序区在变小              
            }  
            return sortArray;  
        }  
        /// <summary>  
        /// 初始大根堆,自底向上地建堆  
        /// 完全二叉树的基本性质,最底层节点是 n/2,所以从 sortArray.Length / 2 开始  
        /// </summary>  
        private static void BuildMaxHeap(int[] sortArray)  
        {  
            for (int i = (sortArray.Length / 2) - 1; i >= 0; i--)  
            {  
                MaxHeapify(sortArray,i, sortArray.Length);  
            }  
        }  
        /// <summary>  
        /// 将指定的节点调整为堆  
        /// </summary>  
        /// <param name="i">需要调整的节点</param>  
        /// <param name="heapSize">堆的大小,也指数组中无序区的长度</param>  
        private static void MaxHeapify(int[] sortArray, int i, int heapSize)  
        {  
            int left = 2 * i + 1; // 左子节点  
            int right = 2 * i + 2; // 右子节点  
            int larger = i; // 临时变量,存放大的节点值  
            // 比较左子节点  
            if (left < heapSize && sortArray[left] > sortArray[larger])  
            {  
                larger = left;  
            }  
            // 比较右子节点  
            if (right < heapSize && sortArray[right] > sortArray[larger])  
            {  
                larger = right;  
            }  
            // 如有子节点大于自身就交换,使大的元素上移。  
            if (i != larger)  
            {  
                Swap(ref sortArray[i], ref sortArray[larger]);  
                MaxHeapify(sortArray, larger, heapSize);  
            }  
        }  
        //数组内元素互换  
        private static void Swap(ref int a, ref int b)  
        {  
            int t;  
            t = a;  
            a = b;  
            b = t;  
        }  
    }  
}

Die Idee der Heap-Sortierung:

Verwenden Sie den Big-Top-Heap (Small-Top-Heap), um das maximale Schlüsselwort (minimales Schlüsselwort) aufzuzeichnen Top of the Heap Funktionen, die es einfach machen, jedes Mal den größten Datensatz (kleinsten Datensatz) aus der Unordnung auszuwählen.

Die Grundidee ist (Big-Top-Heap):

1) Konstruieren Sie die anfängliche Sequenz der zu sortierenden Schlüsselwörter (R1, R2...Rn) in einem Big-Top-Heap Heap ist der anfängliche ungeordnete Bereich;

2) Tauschen Sie das oberste Element R[1] mit dem letzten Element R[n] aus und erhalten Sie einen neuen ungeordneten Bereich (R1, R2,... .Rn-1) und die neue geordnete Fläche (Rn) und erfüllen R[1,2...n-1]<=R[n];

3) Aufgrund des neuen Nachaustauschs R[1] auf Die Oberseite des Heaps kann die Natur des Heaps verletzen, daher muss der aktuelle ungeordnete Bereich (R1, R2, ... Rn-1) an einen neuen Heap angepasst werden, und dann müssen R[1] und der ungeordnete Bereich angepasst werden erneut angepasst werden. Das letzte Element wird ausgetauscht, um einen neuen ungeordneten Bereich (R1, R2...Rn-2) und einen neuen geordneten Bereich (Rn-1, Rn) zu erhalten. Dieser Vorgang wird wiederholt, bis die Anzahl der Elemente im geordneten Bereich n-1 beträgt. Anschließend ist der gesamte Sortiervorgang abgeschlossen.

Der Vorgang ist wie folgt:

1) Initialisieren Sie den Heap: Konstruieren Sie R[1..n] als Heap;

2) Konvertieren Sie das oberste Element von Der aktuelle ungeordnete Bereich im Heap R[1] tauscht mit dem letzten Datensatz im Bereich aus und passt dann den neuen ungeordneten Bereich an den neuen Heap an.

Daher sind für die Heap-Sortierung die beiden wichtigsten Vorgänge das Erstellen des anfänglichen Heaps und des Anpassungs-Heaps. Tatsächlich ist das Erstellen des anfänglichen Heaps der Prozess der Anpassung des Heaps, das Erstellen des anfänglichen Heaps jedoch für alle Nicht-Blattknoten. Nehmen Sie Anpassungen vor.


Das Obige ist der Inhalt der C#-Heap-Sortierung. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!


Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel:C#-EinfügungssortierungNächster Artikel:C#-Einfügungssortierung