C++ で基数ソート アルゴリズムを使用する方法

C で基数並べ替えアルゴリズムを使用する方法

基数並べ替えアルゴリズムは、並べ替え対象の要素を有限の桁のセットに分割する非比較並べ替えアルゴリズムです。並べ替えを完了します。 C では、基数ソート アルゴリズムを使用して整数のセットをソートできます。以下では、特定のコード例を使用して、基数ソート アルゴリズムを実装する方法を詳しく説明します。

1. アルゴリズムのアイデア
   基数ソート アルゴリズムのアイデアは、ソート対象の要素を限られたデジタル ビットのセットに分割し、各ビットで順番に要素をソートすることです。各ビットのソートが完了すると、そのビットの順序に従って要素が再編成され、すべてのビットがソートされるまで次のビットのソートが続けられます。
2. 具体的な実装手順
   (1) まず、ソート対象となる全要素の最大値の桁数を決定する必要があります。これにより、ソートを何ラウンド行う必要があるかが決まります。

(2) 次に、補助配列とカウント配列を作成する必要があります。補助配列は並べ替え処理中に一時的な結果を保存するために使用され、計数配列は各数値の出現回数を記録するために使用されます。

(3) 次に、複数回の並べ替えを実行する必要があります。ソートの各ラウンドでは、現在のビット サイズに従って配列が再編成されます。

(4) ソートの各ラウンドでは、ソート対象の配列を走査し、各要素の現在のビット値をインデックスとして使用し、要素を対応するバケットに入れる必要があります。

(5) 次に、各バケット内の要素の数をカウントする必要があります。これは、カウント配列を使用して記録できます。

(6) 次に、配列を数えることによって、補助配列内の各バケット内の要素の位置を決定する必要があります。これは、配列内の要素のプレフィックスの合計をカウントすることで判断できます。

(7) 最後に、補助配列の要素をソート対象の配列に上書きして、一連のソートを完了します。

(8) すべてのビットがソートされるまで、手順 (3) ～ (7) を繰り返します。

3. コード例
   次は、C を使用して基数ソート アルゴリズムを実装するコード例です。

#include <iostream>
#include <vector>

using namespace std;

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    int digit = 1;
    vector<int> temp(arr.size());
    while (maxVal / digit > 0) {
        vector<int> count(10, 0);

        for (int i = 0; i < arr.size(); i++) {
            count[(arr[i] / digit) % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

        for (int i = 0; i < arr.size(); i++) {
            arr[i] = temp[i];
        }

        digit *= 10;
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    cout << "排序结果：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

上記のコード例では、まず、ソートされる配列 何ラウンドのソートが必要かを決定する最大値。次に、補助配列とカウント配列を作成しました。次に、複数回のソートを実行して、現在のビット サイズに従って配列を再構成します。最後に、ソートした結果を出力します。

要約:
基数ソート アルゴリズムを通じて、C で整数のセットをソートできます。基数ソート アルゴリズムの中心的な考え方は、ソート対象の要素を限られた数値ビットのセットに分割し、各ビットで順番に要素をソートすることです。この非比較ソート アルゴリズムは、整数のセットのソート問題を効果的に処理できます。

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