C++ でカウントソートアルゴリズムを使用する方法

C でのカウント並べ替えアルゴリズムの使用方法

カウント並べ替えアルゴリズムは、比較的シンプルで効率的な並べ替えアルゴリズムであり、整数シーケンスが並べ替えられるシナリオに適しています。その基本的な考え方は、各要素の前にそれよりも小さい要素がいくつあるかを判断し、それによって順序付けされた配列内のその位置を決定することです。

カウント ソート アルゴリズムの手順は次のとおりです。

1. ソートする配列内の最大値を見つけて、カウント配列の長さを決定します。
2. 最大値に 1 を加えた長さの count 配列を作成し、0 に初期化します。
3. 並べ替える配列を走査し、各要素の出現数をカウントし、統計結果を count 配列に保存します。
4. 各位置の値が前の位置の値の合計と等しくなるように、カウント配列を変換します。
5. ソート結果を保存するために、ソート対象の配列と同じ長さの一時配列を作成します。
6. 並べ替える配列を後ろから前に走査し、count 配列に基づいて並べ替え結果内の各要素の位置を決定し、要素を一時配列に格納します。
7. 一時配列の結果を並べ替える配列にコピーして並べ替えを完了します。

以下は、C 言語で実装されたカウント並べ替えアルゴリズムのサンプル コードです:

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

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

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

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

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

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

    cout << "排序后的数组：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

上記のコードでは、補助的なカウント配列を使用して各要素の出現をカウントします。を倍加し、変形によりソート結果内の各要素の位置を計算します。最後に、並べ替えた結果を元の配列にコピーします。

上記のサンプル コードを通じて、カウント ソート アルゴリズムの実装プロセスを確認できます。その時間計算量は O(n k) です。ここで、n はソートされるシーケンスの長さ、k は最大値です要素値と最小要素の値の差に1を加算します。

要約すると、カウンティング ソート アルゴリズムは、整数シーケンスがソートされるシナリオに適した、シンプルだが効率的なソート アルゴリズムです。適切なデータ構造とアルゴリズムを使用することで、並べ替えタスクをより適切に実行できます。

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