Comment écrire un algorithme de tri par tas en utilisant C#

Comment utiliser C# pour écrire un algorithme de tri de tas

Heap Sort est un algorithme de tri basé sur un tas binaire complet, et sa complexité temporelle est O(nlogn). Dans cet article, nous allons écrire l'algorithme de tri par tas en utilisant C# et fournir des exemples de code détaillés.

1. Construire un tas

Dans l'algorithme de tri des tas, vous devez d'abord créer un tas maximum (ou un tas min). La propriété du tas max est que la valeur du nœud parent est supérieure ou égale à la valeur de son nœud enfant, alors que l'inverse est vrai pour le tas min.

Afin de construire un tas maximum, nous pouvons utiliser un tableau pour représenter le tas. Les nœuds du tas sont disposés par ordre hiérarchique. Étant donné un index de nœud i, nous pouvons trouver l'index de ses nœuds parent et enfant par :

• Indice du nœud parent = (i - 1) / 2
• Indice du nœud enfant gauche = 2 * i + 1
• Nœud enfant droit index = 2 * i + 2

En utilisant ces indices, nous pouvons facilement nous déplacer dans le tas et pousser les grands (ou petits) éléments vers le haut du tas.

Voici un exemple de code pour implémenter le tas max en utilisant 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. Tri du tas

Après avoir construit le tas max, nous pouvons utiliser l'algorithme de tri par tas pour trier le tableau. L'idée du tri par tas est de permuter continuellement le plus grand élément vers la fin du tableau et de réduire la plage du tableau à trier. Les étapes spécifiques sont les suivantes :

• Construisez le tas maximum
• Échangez l'élément supérieur et le dernier élément du tas
• Réajustez le tas
• Répétez les étapes ci-dessus jusqu'à ce qu'il ne reste qu'un seul élément dans le tableau à trier

Ce qui suit est un tri par tas utilisant un exemple de code C# pour :

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. Code de test

Pour vérifier que notre algorithme de tri par tas est correct, nous pouvons écrire du code de test qui trie un tableau généré aléatoirement et affiche les résultats pour vérification. Voici un exemple de code de test de tri par tas écrit en C# :

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

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

4. Résumé

Grâce aux étapes ci-dessus, nous avons écrit avec succès un algorithme de tri par tas en utilisant C# et fourni des exemples de code détaillés. Le tri par tas est un algorithme de tri efficace qui offre de bonnes performances dans la plupart des cas. J'espère que cet article vous aidera à comprendre et à implémenter l'algorithme de tri par tas !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!