エントリーレベルのデータベースアルゴリズム [パート 2]

前回の記事「エントリーレベルのデータベースのアルゴリズム [I]」では、いくつかのデータアルゴリズムを紹介しました。ここでは、引き続きいくつかの基本的なソートアルゴリズムを紹介します。

バブルソート

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

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

プログラミング例: 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の場合
        { 
             (b[j]>b[j+1])の場合
            {
                temp = b[j];
                b[j] = b[j+1];
                b[j+1] = 一時;
            }
        }
    }
    cout<< "ソートは次のようになります:" ; 
     ( int i=0;i<10;i++ )の場合
    {
        カウント<  " " ;
    }
    カウント< 
 }

パフォーマンス分析:時間計算量 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の場合
      { 
         整数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++ )の場合
   {
         カウント<  " " ;
   }
   カウント< 
 }

パフォーマンス分析:ヒルソートの時間計算量は少々複雑です。特定の「増分」に応じて変化します。ここでは、著者は 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); 
    古い低値= 低値; 
    古い高=高;
    低い
    {
        while(*(b+high)>*(b+low)&&low  --;  
        Sawp(b+low,b+high);
        while(*(b+low)<*(b+high)&&low 
        Sawp(b+low,b+high);
    }
    if(古い低
    {
        クイックソート(b,Old_low,low-1);
    }
    if(高+1 
    {
        クイックソート(b,high+1,Old_high);
    }
 }
 //スワップ関数
void Sawp( int *a, int *b)
 { 
    整数 温度; 
    温度=*a;
    *a=*b;
    *b=一時;
 }