小白学アルゴリズム2.8——カウントソート

小白学アルゴリズム2.8——カウントソート
ラベル:白白学アルゴリズム
1.カウントソートアルゴリズム
カウントソートは場合によっては比較的速いソートアルゴリズムであり,時間的複雑度はO(N)である.比較に基づくソートアルゴリズムは時間的複雑度が最も低いのがO(NlogN+K)であるため,カウントソートは非比較に基づくアルゴリズムである.カウントソートの使用条件の制限は比較的多く、ソートされる配列について初歩的な理解が必要である.例えば、要求されるソートデータは一般的に整数であり、ソートされる配列の最大値と最小値の差は大きすぎるべきではない.カウントソートは、年齢や身長などのデータをソートするためによく使用されます.
カウントソートの考え方は,データの出現回数に応じてソートすることである.カウントソートは、典型的には空間的に時間を交換するアルゴリズムであり、カウントソートには補助配列b[max+1]が必要であり、maxはソートされる配列の中で最大の数値を表す.並べ替えられる配列a[n]を巡回し、a[n]の各数値についてb[a[i]]++の動作を行うことで、各数a[i]が出現した回数を記録し、配列b[max+1]を巡回し、左から右への出力値が0でない要素を下付きにすればよい.
2.カウントソート実装

void countingSort(int* a, int n)
{
    int i, j;//i a[n]  ，j b[max+1]  
    //find max
    int max = a[0];
    for (i=1; i<n; i++)
        if (max < a[i]) max = a[i];
    //initialize b[max+1]，   0
    int* b = new int[max+1];
    for (j=0; j<max+1; j++)
        b[j] = 0;
    //counting
    for (i=0; i<n; i++)
        b[a[i]]++;
    //output
    for (i=0, j=0; j<max+1; j++)
    {
        while (b[j]!=0)
        {
            a[i++] = j;
            b[j] = b[j] - 1;
        }
    }

    delete []b;
}

3.まとめ

プログラムは、並べ替えられる配列の最小値minを見つけるなど、最適化を継続することができ、補助配列のサイズはmax-min+1であり、空間の複雑さを低減することができ、負の数の並べ替え

を行うことができる.

カウントソートは安定ソートであるが、本稿のコードは体現できない.安定したカウントソートを実現するには3番目の補助配列が必要である場合、具体的なアルゴリズムは白学アルゴリズム2.9-基数ソート

を参照することができる.