Comment utiliser l'algorithme de tri par tas en C++

Comment utiliser l'algorithme de tri par tas en C++

Le tri par tas est un algorithme de tri couramment utilisé qui tire parti des propriétés du tas pour le tri. Le tri en tas est divisé en deux étapes : la création du tas et le tri. Dans cet article, nous apprendrons comment implémenter l'algorithme de tri par tas à l'aide du langage C++ et donnerons des exemples de code spécifiques.

1. La définition et les propriétés d'un tas
   Un tas est un arbre binaire complet, qui peut être divisé en deux types : le tas maximum et le tas minimum. La valeur de n'importe quel nœud dans le tas max est supérieure ou égale à la valeur de ses nœuds enfants, et la valeur de n'importe quel nœud dans le tas min est inférieure ou égale à la valeur de ses nœuds enfants. Dans l'algorithme de tri par tas, nous utilisons généralement le tas maximum.

L'implémentation du tas peut être représentée par un tableau, et l'indice du tableau peut représenter le numéro de nœud dans le tas. Pour tout nœud i, son nœud parent est (i-1)/2, son nœud enfant gauche est 2i+1 et son nœud enfant droit est 2i+2.

2. Algorithme de création de tas
   L'algorithme de création de tas est la première étape du tri de tas. Son objectif est de construire un tableau non ordonné en un tas. L'idée de construire un tas est de partir du dernier nœud non-feuille du tableau et d'effectuer une opération de descente sur chaque nœud afin qu'il réponde aux propriétés d'un tas.

Ce qui suit est un exemple de code C++ de l'algorithme de création de tas :

// 下沉操作，将指定节点下沉到合适的位置
void downAdjust(int arr[], int parent, int length) {
    int child = 2 * parent + 1; // 左子节点的下标
    int temp = arr[parent]; // 保存要下沉的节点的值
    
    while (child < length) {
        // 如果有右子节点，且右子节点的值大于左子节点的值，则选择右子节点
        if (child+1 < length && arr[child] < arr[child+1]) {
            child++;
        }
        
        // 如果父节点的值大于等于子节点的值，则下沉结束
        if (temp >= arr[child]) {
            break;
        }
        
        // 将子节点的值上移，代替父节点
        arr[parent] = arr[child];
        parent = child;
        child = 2 * parent + 1;
    }
    
    // 将要下沉的节点插入合适的位置
    arr[parent] = temp;
}

// 建堆算法，将无序数组构建成最大堆
void buildHeap(int arr[], int length) {
    // 从最后一个非叶子节点开始，依次进行下沉操作
    for (int i = (length-2) / 2; i >= 0; i--) {
        downAdjust(arr, i, length);
    }
}

3. Algorithme de tri
   Une fois la construction du tas terminée, nous pouvons effectuer une opération de tri. L'idée du tri est de retirer l'élément supérieur. du tas à chaque fois et échangez-le avec l'élément à la fin du tas. Puis réenfoncez les parties restantes.

Ce qui suit est un exemple de code C++ de l'algorithme de tri par tas :

// 堆排序算法
void heapSort(int arr[], int length) {
    // 1. 构建最大堆
    buildHeap(arr, length);
    
    // 2. 排序
    for (int i = length - 1; i > 0; i--) {
        // 将堆顶元素与堆尾元素交换
        swap(arr[i], arr[0]);
        
        // 对剩下的部分重新进行下沉操作
        downAdjust(arr, 0, i);
    }
}

4. Exemple et test
   Ce qui suit est un exemple et un test utilisant l'algorithme de tri par tas :

#include <iostream>

// 输出数组元素
void printArray(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// 主函数
int main() {
    int arr[] = {4, 1, 3, 9, 7};
    int length = sizeof(arr) / sizeof(int);
    
    std::cout << "排序前的数组：" << std::endl;
    printArray(arr, length);
    
    // 使用堆排序算法进行排序
    heapSort(arr, length);
    
    std::cout << "排序后的数组：" << std::endl;
    printArray(arr, length);
    
    return 0;
}

Le résultat de sortie est :

排序前的数组：
4 1 3 9 7 
排序后的数组：
1 3 4 7 9 

Avec Dans l'exemple et le test ci-dessus, nous pouvons voir que l'algorithme de tri par tas implémenté en C++ peut trier correctement le tableau.

Résumé :
Cet article présente comment utiliser le langage C++ pour implémenter l'algorithme de tri par tas et donne des exemples de code spécifiques. Le cœur de l'algorithme de tri du tas réside dans les deux étapes de construction et de tri du tas. L'idée de construire un tas est de démarrer l'opération de descente à partir du dernier nœud non-feuille. l'élément supérieur du tas à chaque fois et échangez-le avec l'élément à la fin du tas, et réenfoncez les parties restantes. Grâce à des tests réels, nous pouvons vérifier l'exactitude et la stabilité de 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!