Maîtriser les algorithmes de tri courants en C++

C++ est un langage de programmation largement utilisé en programmation informatique, et les algorithmes de tri sont l'un des algorithmes couramment utilisés en programmation. La maîtrise des algorithmes de tri peut améliorer votre capacité à écrire des programmes efficaces et améliorer vos compétences en programmation. Cet article présentera les algorithmes de tri couramment utilisés en C++.

1. Tri à bulles

Le tri à bulles est un algorithme de tri de base qui réalise le tri en comparant les éléments adjacents en séquence et en échangeant des éléments plus gros jusqu'à la fin de la séquence. Plus précisément, le tri à bulles compare les tailles des éléments adjacents à chaque tour et échange les éléments plus grands vers l'arrière jusqu'à ce que le dernier élément soit trié.

Le code C++ est le suivant :

void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

2. Tri par sélection

Le tri par sélection est un algorithme de tri simple. Il sélectionne à chaque fois le plus petit élément de la partie non triée et le place à la fin de la partie triée, implémentant ainsi le tri. . Plus précisément, le tri par sélection sélectionne le plus petit élément à chaque tour et l'échange avec l'élément à la position actuelle.

Le code C++ est le suivant :

void selectionSort(int arr[], int n)
{
    int minIndex, temp;
    for (int i = 0; i < n - 1; i++) {
        minIndex = i; // 记录最小元素的位置
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换元素
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

3. Tri par insertion

Le tri par insertion est un algorithme de tri simple et intuitif qui insère un élément dans une séquence déjà triée pour obtenir une séquence triée plus longue. Plus précisément, chaque cycle de tri par insertion insère un élément dans le sous-tableau trié et déplace les éléments restants vers l'arrière.

Le code C++ est le suivant :

void insertionSort(int arr[], int n)
{
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i]; // 待插入的元素
        j = i - 1;
        // 将大于待插入元素的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        // 将待插入元素插入到正确的位置
        arr[j+1] = key;
    }
}

4. Tri rapide

Le tri rapide est un algorithme de tri efficace. Il divise la séquence en deux parties en sélectionnant un élément pivot, une partie est plus petite que l'élément pivot et l'autre. L'autre partie est plus grande que l'élément pivot et trie les deux sous-séquences de manière récursive. Plus précisément, le tri rapide sélectionne un élément pivot à chaque tour et place les éléments plus petits que l'élément pivot à gauche de l'élément pivot et les éléments plus grands que l'élément pivot à droite. Ensuite, les sous-séquences gauche et droite sont triées récursivement de la même manière.

Le code C++ est le suivant :

void quickSort(int arr[], int left, int right)
{
    int i = left, j = right;
    int pivot = arr[(left + right) / 2]; // 选择枢纽元素
    while (i <= j) {
        // 找到左侧大于枢纽元素的元素
        while (arr[i] < pivot) {
            i++;
        }
        // 找到右侧小于枢纽元素的元素
        while (arr[j] > pivot) {
            j--;
        }
        // 交换左右元素
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 递归排序左侧和右侧的子序列
    if (left < j) {
        quickSort(arr, left, j);
    }
    if (i < right) {
        quickSort(arr, i, right);
    }
}

5. Tri par fusion

Le tri par fusion est un algorithme de tri classique diviser pour régner. Il divise la séquence en deux sous-séquences, trie chaque sous-séquence séparément et fusionne enfin les deux sous-séquences. . Plus précisément, le tri par fusion divise d'abord la séquence en deux sous-séquences, trie les deux sous-séquences de manière récursive, puis fusionne les deux sous-séquences ordonnées en une seule séquence ordonnée.

Le code C++ est le suivant :

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    // 将数据拷贝到两个临时数组中
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0; // 左侧子数组的索引
    j = 0; // 右侧子数组的索引
    k = left; // 合并后的数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 将左侧子数组的剩余元素拷贝到合并后的数组中
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // 将右侧子数组的剩余元素拷贝到合并后的数组中
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 递归排序左侧和右侧的子序列
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 合并两个有序子数组
        merge(arr, left, mid, right);
    }
}

Voici les cinq algorithmes de tri couramment utilisés en C++. Même si les algorithmes peuvent sembler ennuyeux, ils constituent une partie importante de la programmation. En apprenant les algorithmes de tri, nous pouvons améliorer l’efficacité et la qualité de la programmation.

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!