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

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

Le tri par fusion est un algorithme de tri classique. Il utilise l'idée de la méthode diviser pour régner pour diviser la séquence à trier en deux sous-séquences, les trier. séparément, puis combinez les deux sous-séquences ordonnées pour fusionner en une séquence ordonnée. Ci-dessous, nous présenterons comment utiliser le langage C++ pour implémenter l'algorithme de tri par fusion et donnerons des exemples de code spécifiques.

1. Idée d'algorithme

L'idée principale du tri par fusion est de diviser la séquence à trier en plusieurs sous-séquences, puis d'effectuer un tri d'appels récursifs sur les sous-séquences, et enfin de fusionner les sous-séquences triées.

Les étapes spécifiques sont les suivantes :
1) Si la longueur de la séquence est 1, cela signifie qu'elle est déjà ordonnée et renvoie directement
2) Divisez la séquence en deux sous-séquences de manière égale et effectuez un tri d'appels récursifs sur les deux sous-séquences
3) Combinez les deux sous-séquences avec La séquence ordinale est fusionnée en une séquence ordonnée

2. Exemple de code

Ce qui suit est un exemple de code d'utilisation du langage C++ pour implémenter l'algorithme de tri par fusion :

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序子序列
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left;    // 左子序列起始索引
    int j = mid + 1; // 右子序列起始索引
    int k = 0;       // 临时数组起始索引
    vector<int> temp(right - left + 1); // 临时数组

    // 比较两个子序列的元素，将较小的元素放入临时数组中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余的元素复制到临时数组中
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将临时数组的元素复制回原数组
    for (int m = 0; m < k; ++m) {
        arr[left + m] = temp[m];
    }
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 递归调用排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个有序子序列
        merge(arr, left, mid, right);
    }
}

// 归并排序函数
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

int main() {
    vector<int> arr = {4, 6, 2, 8, 9, 1, 5, 3, 7};

    // 调用归并排序函数
    mergeSort(arr);

    // 输出排序结果
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Le code ci-dessus est un exemple d'utilisation de C++ pour implémenter l'algorithme de tri par fusion. Tout d'abord, une fonction merge函数，用来合并两个有序子序列。然后定义了mergeSort函数，用来进行归并排序的递归调用。最后，在main函数中调用mergeSort trie la séquence à trier et génère le résultat trié.

3. Résumé

L'algorithme de tri par fusion est un algorithme de tri efficace et stable avec une complexité temporelle de O(nlogn). Grâce à des appels récursifs et à des opérations de fusion, le tri par fusion peut diviser la séquence à trier en petits blocs pour le tri, puis fusionner les sous-séquences ordonnées en une séquence ordonnée. Grâce à des exemples de code spécifiques implémentés en langage C++, nous pouvons mieux comprendre et maîtriser le processus d'implémentation de l'algorithme de tri par fusion.

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!