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

前回は著者の指示に従って、データ構造におけるクエリ アルゴリズムといくつかのソート アルゴリズムを確認しました。今回は著者の指示に従って、基本的なソート アルゴリズムをいくつか学習します。

選択ソート

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

アルゴリズムのアイデア:毎回、ソートするデータ要素から最小 (または最大) の要素を選択し、ソートするすべてのデータ要素がソートされるまで、ソートされたシーケンスの最後に配置します。

例: int b[10]={77,1,65,13,​​81,93,10,5,23,17}

 //単純な選択ソート 
 voidシンプルセレクト( int b[10])
 { 
    整数温度; 
    整数i; 
     (i=0;i<9;i++)の場合
    { 
         ( int j=i+1;j<9;j++)の場合
        { 
            もし(b[i]>b[j])
            {
                temp = b [i];
                b[i] = b[j];
                b[j] = 一時;
            }
        }
    }
    cout<< "ソートは次のようになります:" ; 
     ( int i=0;i<10;i++ )の場合
    {
        cout<<b[i]<< " " ;
    }
    cout<<endl;
 }

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

ヒープソート

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

アルゴリズムのアイデア:実際、ヒープ ソートは単純な選択ソートの進化形であり、その主な機能は比較回数を減らすことです。ヒープとは何ですか?シーケンスを完全な二分木と見なすと、完全な二分木内のすべての非終端ノードの値は、その左と右の子ノードの値よりも大きくありません（または小さくありません）。これをヒープと呼ぶことができます。ヒープの特性から、ヒープの最上部が最大キーワード (または最小キーワード) であることがわかります。ヒープの最上部を出力した後、残りの要素で別のヒープを構築し、最上部を出力します。この処理を繰り返し実行することで、順序付けられたシーケンスを取得できます。この処理はヒープソートと呼ばれます。

ヒープソートは主に 2 つのステップに分かれます。

1. 順序付けられていないシーケンスからヒープを構築します。
2. 最上位の要素を出力し、新しいヒープを作成します。

例: int b[10]={77,1,65,13,​​81,93,10,5,23,17}

 //ヒープソート 
 voidヒープソート( int b[10])
 { 
     voidヒープ調整( int b[10], int min, int max); 
     void Sawp( int *a, int *b); 
    整数i; 
     //バイナリツリーが完成しているので、ヒープ変換は最後の非リーフノードから開始されます 
     (i=9/2;i>=0;i--)の場合
    {
        ヒープ調整(b,i,9);
    } 
     //ヒープの一番上のデータを取り出して再度ソートする 
     (i=9;i>0;i--)の場合
    {
        sawp(&b[i],&b[0]);
        ヒープ調整(b,0,i-1);
    }
 }
 //ヒープ調整（トップヒープが大きい）  
 //最小データは配列の開始位置を調整する必要がある 
 //最大データはデータの終了位置を調整する必要がある 
 voidヒープ調整( int b[10], int最小値, int最大値)
 { 
     (max<=min)の場合、戻り値は; 
    整数温度;
    温度=b[分]; 
    整数j; 
     // 子ノードのループを拡張する 
     (j=2*最小;j<=最大;j*=2)の場合
    { 
         //古い子を選択 
         (j<max&&b[j]<b[j+1])の場合
        {
            j++;
        } 
         //スタックの先頭がそれより小さい子は処理されない 
         (temp>b[j])の場合
        { 
            壊す;
        } 
         //大きい数字を小さい数字に置き換える 
        b[最小] = b[j];
        最小値=j;
        }
    b[分]=温度;
 }
 //スワップ関数 
 void Sawp( int *a, int *b)
 { 
    整数温度;
    温度=*a;
    *a=*b;
    *b=一時;
 }

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

マージアルゴリズムは2ウェイマージアルゴリズムとも呼ばれます

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

アルゴリズムのアイデア:初期シーケンスに n 個のレコードが含まれていると仮定すると、これは n 個の順序付けられたサブシーケンスと見なすことができます。各サブシーケンスの長さは 1 で、次に 2 つずつ結合して、長さが 2 または 1 の [n/2] 個のサブシーケンスを取得します (ここでは長さが 1 で、シーケンスの長さが奇数の場合は最後のシーケンスがそのまま残されるため、長さは 1 になります)。次に 2 つずつ結合し、長さ n の順序付けられたシーケンスが得られるまでこのプロセスを繰り返します。

例: int b[10]={77,1,65,13,​​81,93,10,5,23,17}

 //マージソート 
 voidマージソート( int b[10], int d[10], int min, int max)
 { 
     //中央の領域から取得したシーケンスを使用して保存します 
    整数c[10]; 
     void Merge( int c[10], int d[10], int min, int mid, int max); 
     (min==max)d[min]=b[min]の場合; 
    それ以外 
    { 
         // 2つの領域に分割する 
         int中間 = (最小 + 最大) / 2; 
         //このエリアをマージしてソートする 
        マージソート(b,c,min,mid); 
         //このエリアをマージしてソートする 
        マージソート(b,c,mid+1,max); 
         // 2つの領域を結合する 
        マージ(c,d,最小,中間,最大);
    }
 }
 //順序付けられたシーケンス d[min-mid] と d[mid+1-max] を順序付けられたシーケンス c[min-max] にマージします。  
 void Merge( int c[10], int d[10], int min, int mid, int max) をマージします。
 { 
    整数i,j,k; 
     (i=j=min,k=mid+1;j<=mid&&k<=max;i++)の場合
    { 
         (c[j]>c[k])の場合
        {
            d[i] = c[k];
            関数
        } 
        それ以外 
        {
            d[i] = c[j];
            j++;
        }
    } 
     (j<=mid)の場合
    { 
         (;j<=mid;j++,i++)の場合
        {
            d[i] = c[j];
        }
    } 
     (k<=max)の場合
    { 
          (;k<=max;k++,i++)の場合
        {
            d[i] = c[k];
        }
    }
 }

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

要約する

さまざまなアプリケーションや要件に応じて適切なソート方法が異なるため、次の要素を考慮して適切なソート方法を選択してください。

1. ソートするレコードの数 n
2. 安定性の要件
3. ストレージ構造
4. 時間と補助空間の複雑さ

では、ソートアルゴリズムは数多くありますが、どのアルゴリズムをいつ使用すればよいのでしょうか?

n が比較的小さい場合 (たとえば、n<=50)、直接挿入ソートまたは単純選択ソートを使用できます。

シーケンスの初期状態が基本的に順序付けられている場合は、直接挿入ソートまたはバブルソートを選択できます。

n が比較的大きい場合は、時間計算量が O(nlogn) のアルゴリズム（クイックソート、ヒープソート、マージソート）を使用できます。

1. クイックソートは現在、比較ベースの内部ソートに最適な方法と考えられています。ソートされたキーワードがランダムに分散されている場合、クイックソートの平均時間は最短になります。 不安定
2. ヒープ ソートでは、クイック ソートよりも補助スペースが少なくて済み、クイック ソートで発生する可能性のある最悪のシナリオの影響を受けません。 しかし、まだ比較的不安定
3. マージソートは比較的安定していますが、一般的に使用することは推奨されません。実用性が低く、大量の補助スペースを占有する可能性があります。

オリジナルリンク: http://www.cnblogs.com/couhujia/archive/2011/03/25/1994996.html

【編集者のおすすめ】

1. データマイニングにおける10の古典的なアルゴリズムの予備的調査
2. 現在世界で最も重要な古典的アルゴリズムトップ10
3. 面接中にアルゴリズムの質問を解く際にプログラマーが知っておくべきこと
4. 初級データベースアルゴリズム [I]
5. エントリーレベルのデータベースアルゴリズム [パート 2]