Cara menggunakan algoritma isihan baldi dalam C++

Cara menggunakan algoritma isihan baldi dalam C++

Isih Baldi ialah algoritma isihan dengan kerumitan masa linear Ia adalah algoritma isihan berdasarkan konsep baldi. Idea asas pengisihan baldi adalah untuk membahagikan data untuk diisih ke dalam beberapa baldi yang dipesan, dan kemudian mengisih setiap baldi secara berasingan.

Dalam C++, kita boleh menggunakan bekas vektor dan iterator untuk melaksanakan algoritma isihan baldi. Berikut ialah kod sampel khusus:

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

Dalam kod di atas, kami mentakrifkan fungsi BucketSort untuk melaksanakan algoritma pengisihan baldi. Fungsi ini menerima tatasusunan integer arr dan bilangan baldi yang ditetapkan numBuckets sebagai parameter. Mula-mula, kami mencipta vektor dua dimensi baldi untuk mewakili baldi, setiap baldi menyimpan sebahagian daripada elemen. Kami kemudian meletakkan elemen ke dalam baldi yang sepadan berdasarkan nilainya. Seterusnya, unsur-unsur dalam setiap baldi disusun. Akhir sekali, kami meletakkan elemen yang diisih kembali ke dalam tatasusunan asal. 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

Atas ialah kandungan terperinci Cara menggunakan algoritma isihan baldi dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!