バケツソートアルゴリズムの理解とC言語版コードの例

理解:バケツソートはカウントソートの変種であり、カウントソートに隣接するm個の「小さなバケツ」を1つの「大きなバケツ」に入れ、バケツを分けた後、各バケツを並べ替え(一般的には速い列で)し、最後の結果にまとめる.基本思想:バケツ並べ替え仮定シーケンスは、要素を区間[0,1]に均一かつ独立に分布させるランダムなプロセスによって生成される.区間を[0,1)バケツと呼ばれる同じ大きさのn個のサブ区間に分割されている.n個の記録をバケツごとに分散する.複数の記録が同じバケツに分割されている場合、バケツ内ソートが必要となる.最後に、バケツごとの記録列を順番に順番に並べて順序付けシーケンスを記憶する.効率分析:バケツソートの平均時間複雑度が線形のO(N+C),このうちCはバケツ内速排の時間複雑度である.同じNに対してバケツ数Mが大きいほど効率が高くなり,最適な時間的複雑度はO(N)に達する.もちろんバケツソートの空間的複雑度はO(N+M)であり,入力データが非常に膨大であり,バケツの数も非常に多い場合,空間的コストは間違いなく高価である.また、バケツのソートは安定しています.バケツの並べ替えの欠点は、数だけ並んでいるのに数字の範囲が非常に大きい(10個数、数の範囲がさらに0~1000000)場合、10個数でも10000000個のバケツが必要です.
例1:ランダムに5個の数を入力し、大きいから小さいまで出力する.考え方:入力した数値の最大値と最小値に基づいた範囲配列を用いて、1つの数値を入力するたびに、対応する配列のシーケンス番号に数値を挿入します.

#include 
int main()
{
 int a[11],i,j,t;
 //      
 for(i=0;i<=10;i++)
 {
   a[i] = 0;
 }
 //    5  
 for(i = 1;i<=5;i++)
 {
   //           
   scanf("%d",&t);
   //    
   a[t]++;
 }
 //      
 for(i = 10;i>=0;i--)
 {
   for(j=1;j<=a[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 //getchar()      ，           
 //    system("pause");   
 return 0;
}

質問2:0～1000の整数を並べ替え

#include
int main()
{
 int book[1001],i,j,t;
 //      
 for(i=0;i<=1000;i++)
 {
   book[i] = 0;
 }
 //     n，      n  
 scanf("%d",&n);
 for(i = 1;i<=n;i++)
 {
   //           
   scanf("%d",&t);
   //    
   book[t]++;
 }
 //      
 for(i = 1000;i>=0;i--)
 {
   for(j=1;j<=book[i];j++)
     printf("%d",i);
 }
 getchar();getchar();
 return 0;
}