Explication détaillée de la fonction de tri en C++

La fonction de tri en C++ est une fonction fonctionnelle utilisée pour trier les éléments d'un tableau ou d'un conteneur. Le tri peut être effectué par ordre croissant ou décroissant, et différents types de données tels que les types entiers, à virgule flottante et caractères peuvent être triés. Le langage C++ fournit plusieurs fonctions de tri. Cet article présentera en détail l'utilisation et les caractéristiques de ces fonctions de tri.

1. Fonction sort()

La fonction sort() est l'une des fonctions de tri les plus couramment utilisées en C++ STL. Sa fonction est d'organiser les éléments dans un tableau ou un conteneur. L'utilisation de base de la fonction sort() est la suivante :

sort(begin, end);

où start est l'adresse du premier élément du tableau ou du conteneur, end est l'adresse du dernier élément + 1, donc end pointe vers l'adresse vide après le dernier élément. La fonction sort() trie par ordre croissant par défaut. Si vous devez trier par ordre décroissant, vous pouvez transmettre un pointeur de fonction ou une expression lambda comme troisième paramètre.

Ce qui suit est un exemple de code qui montre comment utiliser la fonction sort() pour trier un tableau d'entiers :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

1 2 3 4 5 6 7 8 9

2. fonction stable_sort()

stable_sort () et la fonction sort( ) sont similaires, mais elles garantissent que les positions relatives des éléments ayant la même valeur restent inchangées après le tri. L'utilisation de la fonction stable_sort() est similaire à la fonction sort(). Vous pouvez également transmettre un pointeur de fonction ou une expression lambda comme troisième paramètre. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    stable_sort(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

1 2 3 4 5 6 7 8 9

3. fonction partielle_sort()

la fonctionpartial_sort() peut trier partiellement les éléments du tableau ou du conteneur, c'est-à-dire disposez les k premiers éléments les plus petits du tableau devant (ou triez les k premiers éléments les plus grands devant le tableau). L'utilisation est la suivante :

partial_sort(begin, middle, end);

où start est l'adresse du premier élément du tableau ou du conteneur, end est l'adresse du dernier élément + 1 et middle est un itérateur pointant vers le k-ème élément. Il convient de noter que la fonction partial_sort() garantit uniquement que les k premiers éléments sont ordonnés et que l'ordre des éléments restants n'est pas défini. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    partial_sort(arr, arr + k, arr + n);

    for (int i = 0; i < k; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

1 2 3

4. nth_element() fonction

nth_element() est utilisée pour sélectionner le kième plus petit (ou kième plus grand) élément dans le tableau ou le conteneur, et disposez-le à la k-ième position dans le tableau. L'utilisation est la suivante :

nth_element(begin, middle, end);

où start est l'adresse du premier élément du tableau ou du conteneur, end est l'adresse du dernier élément + 1 et middle est un itérateur pointant vers le k-ième élément. Il convient de noter que la fonction nth_element() garantit uniquement que les k premiers éléments du tableau sont ordonnés, tandis que le kème élément n'est pas trié. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    nth_element(arr, arr + k - 1, arr + n);

    cout << "第 " << k << " 小的数是：" << arr[k - 1] << endl;

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

第 3 小的数是：3

5. fonction make_heap()

la fonctionmake_heap() peut convertir un tableau ou un conteneur en un tas, c'est-à-dire le les éléments du tableau suivent les règles d'un tas binaire trié pour prendre en charge les opérations de tas. L'utilisation est la suivante :

make_heap(begin, end);

où start est l'adresse du premier élément du tableau ou du conteneur, et end est l'adresse du dernier élément + 1. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

9 7 8 6 4 3 5 1 2

6. fonctionpush_heap()

la fonctionpush_heap() peut insérer un nouvel élément dans le tas et réajuster la structure du tas pour satisfaire la nature du tas. L'utilisation est la suivante :

push_heap(begin, end);

où start est l'adresse du premier élément du tableau ou du conteneur, et end est l'adresse du dernier élément. Il convient de noter que le nouvel élément inséré doit être placé à la dernière position du tas. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    arr[n] = 0;

    push_heap(arr, arr + n + 1);

    for (int i = 0; i < n + 1; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

9 7 8 6 4 3 5 1 2 0

7. fonction pop_heap()

la fonction pop_heap() est utilisée pour faire apparaître l'élément supérieur du tas et le réajuster. la structure du tas pour répondre à la nature du tas. L'utilisation est la suivante :

pop_heap(begin, end);

où start est l'adresse du premier élément du tableau ou du conteneur, et end est l'adresse du dernier élément. Il convient de noter qu'après avoir fait éclater l'élément supérieur du tas, la taille du tas doit être réduite de 1. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    pop_heap(arr, arr + n);

    n--;

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

8 7 5 6 4 3 2 1

8. Fonction sort_heap()

La fonction sort_heap() est utilisée pour trier le tas et s'assurer que le tableau trié est dans ordre croissant. L'utilisation est la suivante :

sort_heap(begin, end);

où start est l'adresse du premier élément du tableau ou du conteneur, et end est l'adresse du dernier élément. Il convient de noter que la fonction sort_heap() appellera d'abord la fonction pop_heap() pour faire apparaître l'élément supérieur du tas avant de trier le tas, donc la taille du tableau trié doit être réduite de 1. Voici un exemple de code :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int arr[] = {5, 2, 9, 1, 4, 3, 8, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    make_heap(arr, arr + n);

    sort_heap(arr, arr + n);

    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }

    return 0;
}

Le résultat de l'exécution du code ci-dessus est le suivant :

1 2 3 4 5 6 7 8 9

Résumé

Cet article présente en détail les fonctions de tri courantes en C++, notamment sort(), stable_sort(), partial_sort( ), nth_element(), make_heap(), push_heap(), pop_heap() et sort_heap(). Chacune de ces fonctions de tri possède ses propres caractéristiques et peut répondre à différents besoins de tri. Dans la programmation réelle, il est très important de choisir la fonction de tri appropriée en fonction de la situation spécifique.

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!