クラシックアルゴリズム-カウントソートアルゴリズム

カウントソート:このアルゴリズムは1954年にHarold H.Sewardによって提案された.バケツソートに類似した比較を必要としない線形時間ソートアルゴリズムです.このアルゴリズムは、既知の数の範囲の配列をソートします.その時間的複雑さはO(n)であり,小範囲集合の並べ替えに適している.カウントソートは、0から100までの数値をソートするための最良のアルゴリズムです.例えば、100万人の学生が大学入試に参加する場合、私たちはこの100万人の学生の数学の成績(仮に点数が0から100)を並べ替えたいと思っています.基本思想:与えられた入力シーケンスの各要素xに対して、そのシーケンスの値がxより小さい要素の個数を決定する.この情報があれば、xを最終的な出力シーケンスの正しい位置に直接格納することができる.このデータ範囲の長さの配列Cを作成し、配列内の対応するレコードの出現数をソートする要素ごとに記録します.このアルゴリズムを例として説明すると、ソートする配列がA={1,0,3,1,0,1}であり、ここで最大値が3であり、最小値が0であると仮定すると、長さが4の配列Cを作成する.次に配列Aを1回走査し、A中の各要素の総数を求め、配列Cの対応ユニットに保持する.例えば0の出現回数が2回であれば、C[0]=2である.1の出現回数が4回であればC[1]=4となる.CはAの要素を下にしているので、このようにすると、Aの要素はCの中で自然に秩序化され、ここでは0,1,3(2のカウントは0)の順序で知られ、Cの記録を要素ごとのカウントで出力配列Bに展開し、ソートが完了する.すなわち、B[0]からB[1]までが0 B[2]からB[5]までが1であるように類推される.このソートアルゴリズムは,比較に基づいて実現されず,アルゴリズム複雑度はO(n)であるが,アシスト配列Cが1つ必要であるため空間複雑度が大きく,計算機のメモリが限られているため,このアルゴリズムは範囲の大きい数のソートには適していない.上記はカウントソートアルゴリズムの古典的な解法であるが,この解法は最適ではなく,空間的複雑さも最適化できるはずであるため,その出力の配列Bを全く使わずに直接Cをソートすることができる.アルゴリズムの手順は以下の通りである:1.並べ替えられる配列の中で最大と最小の要素2を探し出す.統計配列中の各値iの要素が出現する回数は、配列Cのi番目の項3に格納される.すべてのカウントを加算(Cの最初の要素から、各項目と前の項目を加算)4.ターゲット配列の逆埋め:各要素iを新しい配列のC(i)番目の項目に配置し、1つの要素を配置するたびにC(i)から1のテストコードを減算します.

#include   
#include   

void print_arry(int *arr,int n)  //    
{  
    int i;  
    for(i = 0; iprintf("%d ", arr[i]);  
    }  
    printf("
");  
}  
void count_sort(int *arr, int *sorted_arr, int n) 
{  
    int *count_arr = (int *)malloc(sizeof(int) * 100);  
    int i;   
    //          
    for(i = 0; i<100; i++)  
        count_arr[i] = 0;  
    //  i      
    for(i = 0;i//           
    for(i = 1; i<100; i++)  
        count_arr[i] += count_arr[i-1];   
    //       （     ），                      
    for(i = n; i>0; i--)  
    {  
        sorted_arr[count_arr[arr[i-1]]-1] = arr[i-1];  
        count_arr[arr[i-1]]--;    
    }   
    free(count_arr);  
}  
int main() 
{  
    int n,i; 
    int *arr,*sorted_arr;
    printf ("      n:");   
    scanf ("%d", &n);  

    arr = (int *)malloc(sizeof(int) * n);  
    sorted_arr = (int *)malloc(sizeof(int) * n);  

    for (i = 0; i100;  
    } 

    printf ("       0~99   ...
");   
    print_arry(arr, n);  
    count_sort(arr, sorted_arr, n);  
    printf ("      ：");   
    print_arry(sorted_arr, n);  
    return 0;   
}  

例結果:入力配列サイズn:5ランダム生成値0~99の配列…41 67,634 0,69並べ替え後の配列:0 34,41,6769