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

Dalam fungsi utama, kami mencipta tatasusunan integer arr dan memulakan beberapa elemen. Kemudian, panggil fungsi BucketSort untuk mengisih. Akhir sekali, kami mengeluarkan kandungan tatasusunan sebelum dan selepas menyusun.

Jalankan kod di atas dan hasil output adalah seperti berikut:

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

Anda boleh melihat bahawa selepas mengisih mengikut algoritma isihan baldi, kandungan tatasusunan telah disusun dalam tertib menaik.

Kerumitan masa pengisihan baldi ialah O(n+k), dengan n ialah bilangan elemen yang hendak diisih dan k ialah bilangan baldi. Memandangkan bilangan baldi ditetapkan, kerumitan masa pengisihan baldi boleh dianggap linear. Walau bagaimanapun, pengisihan baldi mempunyai kerumitan ruang yang tinggi dan memerlukan ruang tambahan untuk menyimpan baldi.

Ringkasnya, menggunakan algoritma isihan baldi dalam C++ boleh mengisih data dengan cepat, cuma sediakan bilangan baldi yang sesuai. Apabila menggunakan algoritma pengisihan baldi, anda perlu mempertimbangkan pengagihan elemen untuk memilih bilangan baldi yang sesuai untuk mengelakkan pembaziran ruang baldi atau pengagihan elemen yang tidak sekata. 🎜

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