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

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

Bucket Sort est un algorithme de tri à complexité temporelle linéaire. C'est un algorithme de tri basé sur le concept de bucket. L'idée de base du tri par buckets est de diviser les données à trier en plusieurs buckets ordonnés, puis de trier chaque bucket séparément.

En C++, nous pouvons utiliser des conteneurs vectoriels et des itérateurs pour implémenter l'algorithme de tri par bucket. Voici un exemple de code spécifique :

#include <iostream>
#include <vector>
#include <algorithm>

void BucketSort(std::vector<int>& arr, int numBuckets) {
    // 创建桶
    std::vector<std::vector<int>> buckets(numBuckets);
    
    // 将元素放入桶中
    for (int i = 0; i < arr.size(); i++) {
        int bucketIdx = arr[i] / numBuckets;
        buckets[bucketIdx].push_back(arr[i]);
    }
    
    // 对每个桶进行排序
    for (int i = 0; i < buckets.size(); i++) {
        std::sort(buckets[i].begin(), buckets[i].end());
    }
    
    // 将排序好的元素放回原数组
    int index = 0;
    for (int i = 0; i < buckets.size(); i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    std::vector<int> arr = {5, 2, 8, 3, 1, 9, 4, 6, 7};
    
    std::cout << "Before sorting: ";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    // 指定桶的数量为3
    BucketSort(arr, 3);
    
    std::cout << "After sorting: ";
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Dans le code ci-dessus, nous définissons une fonction BucketSort pour implémenter l'algorithme de tri du bucket. Cette fonction reçoit un tableau d'entiers arr et le nombre spécifié de buckets numBuckets comme paramètres. Tout d’abord, nous créons un vecteur bidimensionnel buckets pour représenter les buckets, chaque bucket stocke une partie d’éléments. Nous plaçons ensuite les éléments dans les compartiments correspondants en fonction de leurs valeurs. Ensuite, les éléments de chaque compartiment sont triés. Enfin, nous remettons les éléments triés dans le tableau d'origine. BucketSort函数来实现桶排序算法。这个函数接收一个整数数组arr和指定的桶的数量numBuckets作为参数。首先，我们创建了一个二维向量buckets来表示桶，每个桶存放一部分元素。然后，我们根据元素的值将它们放入相应的桶中。接着，对每个桶中的元素进行排序。最后，我们将排序好的元素放回原始数组。

在main函数中，我们创建了一个整数数组arr并初始化了一些元素。然后，调用BucketSort

Dans la fonction main, nous créons un tableau d'entiers arr et initialisons certains éléments. Ensuite, appelez la fonction BucketSort pour trier. Enfin, nous affichons le contenu du tableau avant et après le tri.

Exécutez le code ci-dessus et le résultat de sortie est le suivant :

Before sorting: 5 2 8 3 1 9 4 6 7
After sorting: 1 2 3 4 5 6 7 8 9

Vous pouvez voir qu'après le tri par l'algorithme de tri par compartiment, le contenu du tableau a été classé par ordre croissant.

La complexité temporelle du tri par buckets est O(n+k), où n est le nombre d'éléments à trier et k est le nombre de buckets. Étant donné que le nombre de compartiments est fixe, la complexité temporelle du tri des compartiments peut être considérée comme linéaire. Cependant, le tri par seaux présente une complexité spatiale élevée et nécessite un espace supplémentaire pour stocker les seaux.

En résumé, l'utilisation de l'algorithme de tri par buckets en C++ peut trier rapidement les données, il suffit de fournir un nombre approprié de buckets. Lorsque vous utilisez l'algorithme de tri des compartiments, vous devez prendre en compte la répartition des éléments pour sélectionner un nombre approprié de compartiments afin d'éviter de gaspiller de l'espace dans les compartiments ou une répartition inégale des éléments. 🎜

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!