基本的なプログラミングアルゴリズムを簡単にマスターする（パート2）

[[121970]]

この記事を書く前に、プログラマーの基本的な知識についてお話ししたいと思います。多くの人が自分の仕事の経験について話したり、卒業生にアドバイスをしたりしています。学生は学校でしっかりとしたコンピューターの基礎を築くべきだという彼らの提案に、著者は同意します。しっかりした基礎がなければ、どうやって建物を建てることができるでしょうか?ある程度の基礎知識があれば、深い理論を学ぶのは2倍簡単になります。最初に深い理論に触れてから関連する基礎を学べば、労力は半分で結果は2倍になります。おそらく多くの学生は、今はすぐにでも仕事を始められる人材を採用する企業が多いと言うでしょう。著者がまず言いたいのは、そのような企業は近視眼的な小さな企業に違いないということです。採用しても、非常に優秀な人材を見つけることはできません。たとえそこに行ったとしても、そのような人材は長く留まらないでしょう。なぜなら、そのような企業には発展のビジョンがなく、技術系の人材は発展の見込みがないため転職してしまう可能性があるからです。次に、コンピュータの基礎知識がしっかりしていれば、3 か月以内に会社の技術要件を満たすように学習し、適応できると信じています。

実際、著者が言いたいのは、基本を決して無視してはいけないということです。これ以上長々とせずに、基本的なソートアルゴリズムに直接進みましょう。

基本的なプログラミングアルゴリズム（I）

基本的なプログラミングアルゴリズム（II）

基本的なプログラミングアルゴリズム（III）

バブルソート

使用条件: コレクションの要素はサイズを比較できます

アルゴリズムのアイデア: ソートするレコードを継続的にスキャンします。スキャンするたびに、最小のレコードが見つかり、それが一番上に近づきます。各スキャンではレコードが最終的な最も正しい位置に配置されるため、次のスキャンではレコードを再確認する必要がありません。

プログラミング例: int b[10]={77,1,65,13,81,93,10,5,23,17} はバブルソートされます (ここで概念を混同していました。指摘してくれた zdd に感謝します)

 //バブルソート 
 voidバブル( int b[10])
 {
整数温度;
整数i;
 (i=9;i>0;i--)の場合
{
 ( int j=0;j<i;j++)の場合
{
 (b[j]>b[j+1])の場合
{
 temp = b[j];
                b[j] = b[j+1];
                b[j+1] = 一時;
       }
 }
 }
 cout<< "ソートは次のようになります:" ;
 ( int i=0;i<10;i++ )の場合
{
 cout<<b[i]<< " " ;
 }
 cout<<endl;
 }

パフォーマンス分析: 時間計算量 O(n^2)

シェルソート

使用条件: コレクションの要素はサイズを比較できます

アルゴリズムのアイデア: まず、ソートするレコードのシーケンス全体をいくつかのサブシーケンスに分割し、それぞれに対して直接挿入ソートを実行します。シーケンス全体のレコードが「基本的に順序付けられている」場合は、すべてのレコードに対して直接挿入ソートを実行します。サブシーケンスは単に「セグメントに分割」されるのではなく、特定の「増分」で区切られたレコードによってサブシーケンスが形成されます。そのため、比較して並べ替えるときに、キーワードが小さいレコードは段階的に前に進むのではなく、一定の増分で移動します。「増分」は減少傾向を示し、最終的にこの「増分」は常に 1 になります。このとき、シーケンスは基本的に順序付けられており、並べ替えを完了するために必要な比較と移動はわずかです。シェルソートの増分設定がわかりにくい。一般的に、8 つの数字の「増分」を 4、2、1 に設定することを検討します。 (これはシェルソートの一般的な設定です)。次に、「増分」h(n+1)=3*h(n)+1 を計算する式を作成します (h>N/9 で停止)。この式は増分には最適ではないかもしれませんが、一般的な「増分」設定には適用できます。数字が 8 個ある場合、ここでの増分は 1 です。

プログラミング例: int b[10]={77,1,65,13,81,93,10,5,23,17}はシェルをソートする

//ヒルソートの自動増分は自分で選択する必要があります 
 voidシェルソート( int b[10])
 {
整数h,i;
整数n=10;
 //このループを通して、1と4への増分を計算します 
 (h=1;h<=n/9;h=3*h+1)の場合； 
 
 //インクリメントループ 
 (;h>0;h/=3)の場合
{
 (i=h;i<n;i++)の場合
{
整数j、温度;
 temp = b [i];
 // ソートを挿入 
 (j=ih;j>=0;j=jh)の場合
{
 (b[j]>temp)の場合
{
 b[j+h]=b[j];
 }
それ以外 
 {
壊す;
 }
 }
 b[j+h]=温度;
 }
 }
 cout<< "ソートは次のようになります:" ;
 ( int i=0;i<10;i++ )の場合
{
 cout<<b[i]<< " " ;
 }
 cout<<endl;
 }

パフォーマンス分析: ヒルソートの時間計算量は少々複雑です。特定の「増分」に応じて変化します。ここでは、著者は Yan Weimin の「データ構造」から O(n^3/2) を使用しています。

クイックソート

使用条件: 同等のサイズのコレクション。

アルゴリズムのアイデア: ソートパスを通じて、ソートするレコードは 2 つの独立した部分に分割されます。レコードの一方の部分のキーワードがもう一方の部分のキーワードよりも小さい場合、レコードの 2 つの部分を別々にソートして、最終的に順序付けられたシーケンスに到達できます。ここで重要なポイントは、セグメンテーションの「ベンチマーク」を選択することです。この「ベンチマーク」より大きい場合は 1 つの部分に分割し、この「ベンチマーク」より小さい場合は 1 つの部分に分割する必要があります。ここで、著者はデフォルトでこの部分の最初のレコードを「ベンチマーク」として使用します。

プログラミング例: int b[10]={77,1,65,13,81,93,10,5,23,17}

 //クイックソート 
 voidクイックソート( int *b, int下限, int上限)
 {
 //スワップ関数 
 void Sawp( int *a, int *b);
古い低値= 低値;
古い高=高;
 (低<高)
 {
 (*(b+high)>=*(b+low)&&low<high)high-- の場合;
 Sawp(b+low,b+high);
 (*(b+low)=<*(b+high)&&low<high)low++の場合;
 Sawp(b+low,b+high);
 }
 (Old_low<low-1)の場合
{
クイックソート(b,Old_low,low-1);
 }
 (高+1<古い高)の場合
{
クイックソート(b,high+1,Old_high);
 }
 } 
 
 //スワップ関数 
 void Sawp( int *a, int *b)
 {
整数温度;
温度=*a;
 *a=*b;
 *b=一時;
 }