So verwenden Sie den Bucket-Sortieralgorithmus in C++

So verwenden Sie den Bucket-Sortieralgorithmus in C++

Bucket Sort ist ein Sortieralgorithmus mit linearer Zeitkomplexität. Es ist ein Sortieralgorithmus, der auf dem Bucket-Konzept basiert. Die Grundidee der Bucket-Sortierung besteht darin, die zu sortierenden Daten in mehrere geordnete Buckets aufzuteilen und dann jeden Bucket separat zu sortieren.

In C++ können wir Vektorcontainer und Iteratoren verwenden, um den Bucket-Sortieralgorithmus zu implementieren. Das Folgende ist ein spezifischer Beispielcode:

#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;
}

Im obigen Code definieren wir eine BucketSort-Funktion, um den Bucket-Sortieralgorithmus zu implementieren. Diese Funktion erhält als Parameter ein Integer-Array arr und die angegebene Anzahl an Buckets numBuckets. Zuerst erstellen wir einen zweidimensionalen Vektor buckets, um Buckets darzustellen. Jeder Bucket speichert einen Teil der Elemente. Anschließend platzieren wir die Elemente basierend auf ihren Werten in den entsprechenden Buckets. Als nächstes werden die Elemente in jedem Bucket sortiert. Abschließend fügen wir die sortierten Elemente wieder in das ursprüngliche Array ein. BucketSort函数来实现桶排序算法。这个函数接收一个整数数组arr和指定的桶的数量numBuckets作为参数。首先，我们创建了一个二维向量buckets来表示桶，每个桶存放一部分元素。然后，我们根据元素的值将它们放入相应的桶中。接着，对每个桶中的元素进行排序。最后，我们将排序好的元素放回原始数组。

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

In der Funktion main erstellen wir ein Integer-Array arr und initialisieren einige Elemente. Rufen Sie dann zum Sortieren die Funktion BucketSort auf. Abschließend geben wir den Array-Inhalt vor und nach der Sortierung aus.

Führen Sie den obigen Code aus und das Ausgabeergebnis lautet wie folgt:

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

Sie können sehen, dass nach der Sortierung mit dem Bucket-Sortieralgorithmus der Inhalt des Arrays in aufsteigender Reihenfolge angeordnet wurde.

Die zeitliche Komplexität der Bucket-Sortierung beträgt O(n+k), wobei n die Anzahl der zu sortierenden Elemente und k die Anzahl der Buckets ist. Da die Anzahl der Buckets fest ist, kann die zeitliche Komplexität der Bucket-Sortierung als linear betrachtet werden. Allerdings weist die Eimersortierung einen hohen Platzaufwand auf und erfordert zusätzlichen Platz zum Lagern der Eimer.

Zusammenfassend lässt sich sagen, dass die Verwendung des Bucket-Sortieralgorithmus in C++ Daten schnell sortieren kann, indem einfach eine geeignete Anzahl von Buckets bereitgestellt wird. Wenn Sie den Bucket-Sortieralgorithmus verwenden, müssen Sie die Verteilung der Elemente berücksichtigen, um die entsprechende Anzahl von Buckets auszuwählen, um eine Verschwendung von Bucket-Platz oder eine ungleichmäßige Verteilung der Elemente zu vermeiden. 🎜

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Bucket-Sortieralgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!