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

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

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!