Tri par tas C#

Tri par tas C#

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

L'idée du tri par tas :

Utilisez le tas big top (petit tas supérieur) pour enregistrer le mot-clé maximum (mot-clé minimum) au haut de gamme Fonctionnalités qui simplifient la sélection du plus grand enregistrement (le plus petit enregistrement) du désordre à chaque fois.

L'idée de base est (grand tas) :

1) Construire la séquence initiale de mots-clés à trier (R1, R2....Rn) dans un grand tas. le tas est la zone désordonnée initiale

2) Échangez l'élément supérieur R[1] avec le dernier élément R[n] et obtenez une nouvelle zone désordonnée (R1, R2,... .Rn-1) et la nouvelle zone ordonnée (Rn), et satisfont R[1,2...n-1]<=R[n];

3) En raison du nouveau après échange R[1] sur le haut du tas peut violer la nature du tas, donc la zone non ordonnée actuelle (R1, R2,...Rn-1) doit être ajustée à un nouveau tas, puis R[1] et la zone non ordonnée doivent à réajuster Le dernier élément est échangé pour obtenir une nouvelle zone désordonnée (R1, R2...Rn-2) et une nouvelle zone ordonnée (Rn-1, Rn). Ce processus est répété jusqu'à ce que le nombre d'éléments dans la zone ordonnée soit n-1, puis l'ensemble du processus de tri est terminé.

Le processus de fonctionnement est le suivant :

1) Initialiser le tas : Construire R[1..n] en tant que tas

2) Convertir l'élément supérieur de ; la zone non ordonnée actuelle du tas R[1] échange avec le dernier enregistrement de la plage, puis ajuste la nouvelle zone non ordonnée au nouveau tas.

Par conséquent, pour le tri des tas, les deux opérations les plus importantes sont la construction du tas initial et le tas d'ajustement. En fait, la construction du tas initial est en fait le processus d'ajustement du tas, mais la construction du tas initial l'est. pour tous les nœuds non-feuilles. Effectuez des ajustements.

Ce qui précède est le contenu du tri du tas C#. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !