一番速くて簡単な並べ替え——桶並べ替えsdut 3761
zhuanzai sheng ming！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
http://blog.51cto.com/
この記事は「あは磊」のブログから出ていますので、ぜひこのソースを残してください。 http://ahalei.blog.51cto.com/4767671/1362789
https://blog.csdn.net/ahalei/article/details/19825419
【アルゴリズム】一番速くて簡単な並べ替え——バケツ並べ替え
私たちが住んでいるこの世界は至るところ並べられています。列に立つ時は身長によって並べられます。試験の順位は点数によって並べられます。ネットショッピングの時は価格によって並べられます。メールボックスの中のメールは時間によって並べられます。つまり、多くのものは順番に並べられます。並べ替えはどこにでもあります。具体的な例を挙げて並べ替えアルゴリズムを紹介します。
まず登場した私たちの主人公のふんちゃん、上のかわいい子供です。期末試験が終わったら、先生はクラスメートの点数を高い順に並べます。フンさんのクラスには5人のクラスメートしかいません。この5人のクラスメートはそれぞれ5点、3点、5点、2点と8点を取っています。次にスコアを大きいから小さいまで並べ替えて、並べ替えた後は8 5 3 2です。何かいい方法がありますか？プログラムを作成して、コンピュータにランダムに5つの数を読み込ませてから、この5つの数を大から小出力にします。まず考えてみてください。少なくとも15分後に下を見てください。
ここでは一次元配列を借りるだけでこの問題を解決できます。本当によく考えてみてください。
まず、サイズ11の配列int a[11]を申請したいです。OK今は11の変数があります。番号はa[0]~a[10]からです。最初はa[0]~a[10]を0に初期化しました。これらの点数はまだ誰も得られていません。例えばa[0]が0に等しいということは、現在はまだ0点を得た人がいないということであり、同理a[1]が0に等しいということは、現在はまだ1点を得た人がいないということです。
次から各個人の点数を処理します。一番目の人の点数は5点です。a[5]に対応する値をもとの基礎に1を追加します。a[5]の値は0から1に変更します。5点は一回現れました。
二人目のスコアは3点です。a[3]に対応する値をもとに1を追加します。a[3]の値は0から1に変更されます。3分に1回現れたことを表します。
注意します3人目の点数も5点ですから、a[5]の値はその上でもう1を増やして、a[5]の値は1から2に変えます。5分で二回も現れました。
先ほどの方法で4番目と5人目の点数を処理します。最終結果は次の図です。
ありません。a[0]~a[10]の数値は0点から10点までの点数の出現回数です。次に、私達は出現した点数をプリントアウトすればいいです。何回か現れたら何回プリントします。具体的には以下の通りです。
a[0]は0で、「0」が現れていないと表示し、印刷しない。
a[1]は0で、「1」が現れていないので、印刷しないという意味です。
a[2]は1で、「2」が1回発生したことを示し、2を印刷する。
a[3]は1で、「3」が1回発生したことを示し、3を印刷する。
a[4]は0で、「4」が現れていないので、印刷しないという意味です。
a[5]は2で、「5」が2回発生したことを示し、5を印刷する。
a[6]は0で、「6」が現れていないと表示し、印刷しない。
a[7]は0で、「7」が現れていないので、印刷しないという意味です。
a[8]は1で、「8」が1回発生したことを示し、8を印刷する。
a[9]は0で、「9」が現れたことがなく、印刷しないという意味です。
a[10]は0で、「10」が現れていないので、印刷しないという意味です。
最終画面出力は「2 3 5 5 5 8」で、完全なコードは以下の通りです。
このアルゴリズムは例えば11個の桶があり、番号は0から10までです。一つの数が出るごとに、番号に対応するバケツの中に小さな旗を置いて、最後に数を数えるだけでいいです。例えば、2番の桶の中に小さな旗があります。2が一回現れたことを表します。3号の中に小さな旗があります。3が一回現れたと表しています。5号の中に2つの小さい旗があって、5が2回現れたと表しています。8号の中に小さな旗があります。8が一回現れました。
今は、n個の0～1000個の整数を入力して、大きいものから小さいものまで並べ替えてみてください。注意してください。データ範囲が0から1000までの整数を並べ替える必要があるなら、私たちは1001個の桶を必要とします。0から1000までの間の個数の出現回数を表します。この点に注意してください。また、ここの各バケツの役割は、「マーク」の個数ごとに出現する回数です。だから、以前の配列aをより適切な名前のbook（bookという単語は記録、マークという意味があります。）に換えることが好きです。コードは下記のようになります。最後に時間の複雑さの問題を言います。コードの6行目の循環は全部でm回（mは桶の個数）、9行目のコードはn回（nは順序待ちの個数）、14行目と15行目は全部でm＋n回循環しました。したがって、並べ替えアルゴリズム全体でm+n+m+n回実行されました。時間複雑さを大文字Oで表しますので、このアルゴリズムの時間複雑さはO（m＋n＋m＋n）すなわちO（2＊（m＋n））です。時間複雑さを言うときは小さな定数を無視でき，最終的なバレル秩序化の時間複雑さはO（m＋n）である。もう一つは、時間の複雑さを表すとき、nとmは大文字のO（M＋N）を使います。 これは非常に速い順序付けアルゴリズムである。バレルの並べ替えは1956年から使われています。このアルゴリズムの基本的な考え方はE.J.Issacです。 R.C.Singletonが持ち出します。前に言ったように、実はこれは本物の樽並べ替えアルゴリズムではなく、真のバケツ並び替えアルゴリズムはこれより複雑です。しかし、ここがアルゴリズム解説の第一編ということを考えると、やはり簡単で分かりやすい方がいいと思います。本当のバケツランキングは後に残してから話しましょう。説明が必要なのは、現在学習されている簡略化されたバージョンのバケツ並び替えアルゴリズムは、本質的にはまだ本物の並べ替えアルゴリズムとは言えないことである。
ti zhauznai 若死を自慢するものはない 2017年5月17日19:14:06読解数：135
並べ替え
Time Limit：1000 MSメモリLimit：65536 KB Problem Description
bLueは年をまたいで贈り物をもらいました。中には大文字と小文字だけを含む文字列が入っています。bLueを手伝ってこの文字列を辞書順に並べ替えてもいいです。（ASCIIコードによって小さい順に並べられます。大文字のASCIIコードは小文字のASCIIコードより小さいです。）彼はAccteptedを奨励します。 Input
入力データは複数のグループ（データグループ数は50を超えない）があり、EOFまで終了します。
各グループのデータに対して、入力行は大文字と小文字だけを含む文字列で、長さは100000を超えません。 Output
データのグループごとに、並べ替えられた文字列が出力されます。 Example Input
HappyNewYear aabAAbbbbbbbbbbbbbbbbbcdAB
Example Output
HNYAaeepprwy AAABBabbbbbbbbbbcd
データ量が大きいので、cinを直接使用することは推奨されません。cout入出力です。
また、最終的な結果は文字列全体を直接出力することで、printf("%c")やputar()などの関数を使って1つずつ文字を出力しないと、タイムアウトの原因になります。 Author 「SDUT Round〓1-Hello 2017年越し大作戦」bLue 分析: このテーマを見て、私の第一の考えは早く並んで、直接にC++の快速排出関数を使って、結果はTLEを知ることができます。
http://blog.51cto.com/
この記事は「あは磊」のブログから出ていますので、ぜひこのソースを残してください。 http://ahalei.blog.51cto.com/4767671/1362789
https://blog.csdn.net/ahalei/article/details/19825419
【アルゴリズム】一番速くて簡単な並べ替え——バケツ並べ替え
私たちが住んでいるこの世界は至るところ並べられています。列に立つ時は身長によって並べられます。試験の順位は点数によって並べられます。ネットショッピングの時は価格によって並べられます。メールボックスの中のメールは時間によって並べられます。つまり、多くのものは順番に並べられます。並べ替えはどこにでもあります。具体的な例を挙げて並べ替えアルゴリズムを紹介します。
まず登場した私たちの主人公のふんちゃん、上のかわいい子供です。期末試験が終わったら、先生はクラスメートの点数を高い順に並べます。フンさんのクラスには5人のクラスメートしかいません。この5人のクラスメートはそれぞれ5点、3点、5点、2点と8点を取っています。次にスコアを大きいから小さいまで並べ替えて、並べ替えた後は8 5 3 2です。何かいい方法がありますか？プログラムを作成して、コンピュータにランダムに5つの数を読み込ませてから、この5つの数を大から小出力にします。まず考えてみてください。少なくとも15分後に下を見てください。
ここでは一次元配列を借りるだけでこの問題を解決できます。本当によく考えてみてください。
まず、サイズ11の配列int a[11]を申請したいです。OK今は11の変数があります。番号はa[0]~a[10]からです。最初はa[0]~a[10]を0に初期化しました。これらの点数はまだ誰も得られていません。例えばa[0]が0に等しいということは、現在はまだ0点を得た人がいないということであり、同理a[1]が0に等しいということは、現在はまだ1点を得た人がいないということです。
次から各個人の点数を処理します。一番目の人の点数は5点です。a[5]に対応する値をもとの基礎に1を追加します。a[5]の値は0から1に変更します。5点は一回現れました。
二人目のスコアは3点です。a[3]に対応する値をもとに1を追加します。a[3]の値は0から1に変更されます。3分に1回現れたことを表します。
注意します3人目の点数も5点ですから、a[5]の値はその上でもう1を増やして、a[5]の値は1から2に変えます。5分で二回も現れました。
先ほどの方法で4番目と5人目の点数を処理します。最終結果は次の図です。
ありません。a[0]~a[10]の数値は0点から10点までの点数の出現回数です。次に、私達は出現した点数をプリントアウトすればいいです。何回か現れたら何回プリントします。具体的には以下の通りです。
a[0]は0で、「0」が現れていないと表示し、印刷しない。
a[1]は0で、「1」が現れていないので、印刷しないという意味です。
a[2]は1で、「2」が1回発生したことを示し、2を印刷する。
a[3]は1で、「3」が1回発生したことを示し、3を印刷する。
a[4]は0で、「4」が現れていないので、印刷しないという意味です。
a[5]は2で、「5」が2回発生したことを示し、5を印刷する。
a[6]は0で、「6」が現れていないと表示し、印刷しない。
a[7]は0で、「7」が現れていないので、印刷しないという意味です。
a[8]は1で、「8」が1回発生したことを示し、8を印刷する。
a[9]は0で、「9」が現れたことがなく、印刷しないという意味です。
a[10]は0で、「10」が現れていないので、印刷しないという意味です。
最終画面出力は「2 3 5 5 5 8」で、完全なコードは以下の通りです。
#include
int main()
{
int a[11],i,j,t;
for(i=0;i<=10;i++)
a[i]=0; // 0
for(i=1;i<=5;i++) // 5
{
scanf("%d",&t); // t
a[t]++; //
}
for(i=0;i<=10;i++) // a[0]~a[10]
for(j=1;j<=a[i];j++) //
printf("%d ",i);
getchar();getchar();
// getchar(); ，
// system("pause");
return 0;
} このアルゴリズムは例えば11個の桶があり、番号は0から10までです。一つの数が出るごとに、番号に対応するバケツの中に小さな旗を置いて、最後に数を数えるだけでいいです。例えば、2番の桶の中に小さな旗があります。2が一回現れたことを表します。3号の中に小さな旗があります。3が一回現れたと表しています。5号の中に2つの小さい旗があって、5が2回現れたと表しています。8号の中に小さな旗があります。8が一回現れました。
今は、n個の0～1000個の整数を入力して、大きいものから小さいものまで並べ替えてみてください。注意してください。データ範囲が0から1000までの整数を並べ替える必要があるなら、私たちは1001個の桶を必要とします。0から1000までの間の個数の出現回数を表します。この点に注意してください。また、ここの各バケツの役割は、「マーク」の個数ごとに出現する回数です。だから、以前の配列aをより適切な名前のbook（bookという単語は記録、マークという意味があります。）に換えることが好きです。コードは下記のようになります。
#include
int main()
{
int book[1001],i,j,t,n;
for(i=0;i<=1000;i++)
book[i]=0;
scanf("%d",&n);// n， n
for(i=1;i<=n;i++)// n ，
{
scanf("%d",&t); // t
book[t]++; // ， t
}
for(i=1000;i>=0;i--) // 1000~0
for(j=1;j<=book[i];j++) //
printf("%d ",i);
getchar();getchar();
return 0;
}
ti zhauznai 若死を自慢するものはない 2017年5月17日19:14:06読解数：135
並べ替え
Time Limit：1000 MSメモリLimit：65536 KB Problem Description
bLueは年をまたいで贈り物をもらいました。中には大文字と小文字だけを含む文字列が入っています。bLueを手伝ってこの文字列を辞書順に並べ替えてもいいです。（ASCIIコードによって小さい順に並べられます。大文字のASCIIコードは小文字のASCIIコードより小さいです。）彼はAccteptedを奨励します。 Input
入力データは複数のグループ（データグループ数は50を超えない）があり、EOFまで終了します。
各グループのデータに対して、入力行は大文字と小文字だけを含む文字列で、長さは100000を超えません。 Output
データのグループごとに、並べ替えられた文字列が出力されます。 Example Input
HappyNewYear aabAAbbbbbbbbbbbbbbbbbcdAB
Example Output
HNYAaeepprwy AAABBabbbbbbbbbbcd
データ量が大きいので、cinを直接使用することは推奨されません。cout入出力です。
また、最終的な結果は文字列全体を直接出力することで、printf("%c")やputar()などの関数を使って1つずつ文字を出力しないと、タイムアウトの原因になります。 Author 「SDUT Round〓1-Hello 2017年越し大作戦」bLue 分析: このテーマを見て、私の第一の考えは早く並んで、直接にC++の快速排出関数を使って、結果はTLEを知ることができます。
#include
using namespace std;
char st1[1212121];
int book[1211];
int main()
{
while(~scanf("%s", st1))
{
int x;
int len = strlen(st1);
for(int i=0;i