Application de la fonction récursive C++ dans l'algorithme diviser pour régner ?

L'algorithme diviser pour régner décompose un gros problème en sous-problèmes plus petits. Les fonctions récursives C++ peuvent implémenter l'algorithme diviser pour régner : sélectionner l'élément de base ; diviser le tableau en deux côtés de l'élément de base ; deux parties ; fusionner les parties triées.

Application C++ de fonctions récursives dans l'algorithme diviser pour régner

L'algorithme diviser pour régner est une stratégie qui décompose un gros problème en sous-problèmes plus petits, puis résout les sous-problèmes de manière récursive. Les fonctions récursives en C++ sont idéales pour implémenter des algorithmes diviser pour régner car elles permettent d'écrire du code facile à comprendre et à déboguer.

Étude de cas sur le tri rapide

Le tri rapide est l'un des algorithmes diviser pour régner les plus populaires. Il trie un tableau non ordonné en suivant ces étapes :

1. Sélectionnez un élément de base.
2. Divisez les éléments du tableau en deux parties : les éléments plus petits que l'élément de base et les éléments plus grands que l'élément de base.
3. Triez ces deux parties de manière récursive.
4. Fusionnez les deux parties triées dans le tableau d'origine.

Voici un exemple d'implémentation d'une fonction de tri rapide en C++ :

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partitionIndex = partition(arr, low, high);  // 获取分区索引
        
        // 递归地排序两部分
        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;  // 指向最终小于基准的元素的索引
    
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

En utilisant cette fonction de tri rapide, vous pouvez trier un tableau comme suit :

int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);

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!