初級データベースアルゴリズム [I]

作者は長い間ブログを更新していませんでした。その理由の一つは、開発したプロジェクトで使用されている技術がすべて古い技術であり、私が接触した知識はすべて業界のロジックプロセスであるため、自分で要約しただけで共有しなかったことです。もう 1 つの理由は、現在 C++ 言語と基本的なコンピューター知識 (アルゴリズムなど) を再学習しているところです。

次のコードは C++ コードです。早速本題に入りましょう。

バイナリ検索はバイナリ検索とも呼ばれます。

使用条件：注文済みセット。

アルゴリズムの考え方:最初に検索対象のレコードが配置されている範囲 (間隔) を決定し、その後、レコードが見つかるか見つからないかになるまで徐々に範囲を狭めていきます。

ポイントは、中間の位置に記録されたキーワードを指定された値と比較することです。指定された値より大きい場合（ここでは、セットが小さいものから大きいものに配置されていると仮定します）、間隔の範囲を狭め（セットの開始->中間の前のポジション）、間隔の中間の位置に記録されたキーワードを指定された値と比較し、位置が見つかるか見つからないかになるまでサイクルを繰り返します。

プログラミング例:整数データ int a[10]={1,5,10,13,17,23,65,77,81,93};

1) これは再帰です(ここでの判断条件の誤りを指摘してくれた仲間のユーザー zdd に感謝します。これは if(min>max) に変更する必要があります)

 //二分探索 
 //配列は特定の順序でなければなりません 
 //パラメータ: ***、最小値、ターゲット (パラメータの型は整数)  
 intバイナリサーチ( int最小値、 int最大値、 int数値)
 { 
     min==maxの場合は-1 を返します。 
     int中間 = (最小 + 最大) / 2; 
     if (a[mid]==num)はmidを返します。 
    それ以外 もし（a[mid] 
    { 
        BinarySearch(mid+1,max,num) を返します。
    } 
    それ以外 
    { 
        BinarySearch(min,mid-1,num) を返します。
    }
 }

2) 非再帰的

//非再帰アルゴリズム 
 int BinarySearch_F( int数値)
 { 
    整数最小値=0; 
    整数最大値=9; 
    整数中間; 
     (最小<=最大)
    {
        中間=(最小+最大)/2; 
         if (a[mid]==num)はmidを返します。 
        それ以外  ( a[mid]>num)max=mid-1の場合; 
        それ以外の場合はmin=mid+1;
    } 
     -1 を返します。
 }

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

挿入ソート

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

アルゴリズムのアイデア:ソートされた順序付きシーケンスにレコードを挿入して、レコード数が 1 増加した新しい順序付きシーケンスを取得します。挿入するレコードは、すでにソートされたシーケンスと順番に比較されます。シーケンス番号が挿入するレコードより大きい場合は、挿入するレコードより小さいシーケンスが見つかるまでシーケンスを 1 つ戻します。このとき、シーケンスの次の位置に挿入され、すべての位置が埋まるまで上記の操作が繰り返されます。

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

// ソートを挿入 
 //ここでtempはセンチネルの位置です 
 //幼少期から成人期まで 
 void挿入ソート()
 { 
    整数温度; 
    整数j; 
     ( int i=1;i<10;i++ )の場合
    {
        temp = b[i]; 
         (j=i-1;j>=0;j--)の場合
        { 
             (b[j]>temp)の場合
            {
                b[j+1] = b[j];
            } 
            それ以外 
            { 
                壊す;
            }
        }
        b[j+1] = 一時;
    }
    cout<< "ソートは次のようになります:" ; 
     ( int i=0;i<10;i++ )の場合
    {
        カウント<  " " ;
    }
    カウント< 
 }

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

バイナリ挿入ソート

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

アルゴリズムの考え方:基本的な考え方は、単純な挿入ソートと似ています。唯一の違いは、挿入位置を見つけることです。単純な挿入ソートでは、順次比較を使用します。ここではバイナリ挿入ソートが改良され、順次検索がバイナリ検索に改良されています。

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

voidバイナリ挿入ソート()
 { 
     int温度、最低、最高、中間; 
    整数j; 
     ( int i=1;i<10;i++)の場合
    {
       最小=0;最大=i-1;
       temp = b [i]; 
        (最小<=最大)
       {
           中間=(最小+最大)/2; 
            (b[mid]>temp)の場合
           {
               最大値=中間-1;
           } 
           それ以外 
           {
                最小=中間+1;
           }
       } 
         (j=i-1;j>=max+1;j--)の場合
       {
            b[j+1] = b[j];
       }
       b[max+1] = 温度;
    }
    cout<< "ソートは次のようになります:" ; 
     ( int i=0;i<10;i++ )の場合
    {
        カウント<  " " ;
    }
    カウント< 
 }