C++ でバケット ソート アルゴリズムを使用する方法

C でのバケット ソート アルゴリズムの使用方法

バケット ソートは、バケットの概念に基づいた線形時間計算量のソート アルゴリズムです。 。バケット並べ替えの基本的な考え方は、並べ替えるデータを順序付けされた複数のバケットに分割し、各バケットを個別に並べ替えることです。

C では、ベクトル コンテナーとイテレータを使用してバケット ソート アルゴリズムを実装できます。以下は具体的なサンプル コードです。

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

上記のコードでは、バケット ソート アルゴリズムを実装する BucketSort 関数を定義します。この関数は、整数配列 arr と指定されたバケット数 numBuckets をパラメーターとして受け取ります。まず、バケットを表す 2 次元ベクトル 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

バケット ソート アルゴリズムによるソート後、配列の内容が昇順に並べられていることがわかります。

バケットソートの時間計算量は O(n k) です。ここで、n はソートされる要素の数、k はバケットの数です。バケットの数は固定されているため、バケットの並べ替えの時間計算量は線形であると考えることができます。ただし、バケットによる並べ替えにはスペースが非常に複雑であり、バケットを保存するために追加のスペースが必要です。

要約すると、C でバケット並べ替えアルゴリズムを使用すると、適切な数のバケットを指定するだけで、データをすばやく並べ替えることができます。バケット並べ替えアルゴリズムを使用する場合は、要素の分布を考慮して適切な数のバケットを選択し、バケット領域の無駄や要素の不均等な分布を避ける必要があります。

以上がC++ でバケット ソート アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。