基本ソートアルゴリズムの8-カウントソート

基本ソートアルゴリズムのまとめと比較の8——カウントソート
1、カウントソート
先に紹介した7種類の並べ替えアルゴリズムはいずれも比較に基づく並べ替えアルゴリズム(CBA式アルゴリズム)に属する.このようなアルゴリズムの共通点は,時間複雑度がO(nlogn)まで最適であることである.次に,今回紹介した3つのアルゴリズムはいずれも非比較アルゴリズムに属し,その時間的複雑度は平均的にO(k・n),kは定数である.
カウントソートはハトの巣ソートとも呼ばれます.カラムの最大数の値と等しい長さの配列で、各要素の出現回数を記録します.次に、レコード配列を巡り、レコードの個数に応じて下付きを印刷します.このソートは数値が小さいときに特に速い.
しかし、特に実用的ではありません.一つは最大数が大きすぎると特大な配列を開けなければならない.2つ目は、配列の下付き文字は非負の整数しか指定できません.

//       
int findMax(int arr[], int lo, int hi)
{
    int max = *(arr + lo);
    while(++lo < hi)
    {
        if (*(arr + lo) > max) max = *(arr + lo);
    }
    return max; 
}

void countSort(int arr[], int lo, int hi)
{
    int maxNum = findMax(arr, lo, hi);
    size_t *count = new size_t[maxNum + 1];    //     maxNum + 1     
    for(int j = 0; j < maxNum + 1; j++) count[j] = 0;    //  
    
    for(int i = lo; i < hi; i++)
    {
        count[*(arr + i)]++;
    }
    
    int *p = arr;
    for(int j = 0; j < maxNum + 1; j++)
    {
        while(count[j]--)
        {
            *p++ = j;
        }
    }
}

アルゴリズムの時間的複雑さはO(2 n)であり,安定であることは明らかである.
カウントソートについてビットマップソートという特殊なバージョンがあります.重複しない非負の整数列にのみ適用されます.その原理は、対応するビット数の数値の有無をメモリの0,1で表すメモリを開くことです.これにより、メモリ容量を大幅に節約し、演算速度を向上させることができます.同様に、彼も特に実用的ではありません!ビットマップのソートに関する内容は説明されません.