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

[[121972]]

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

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

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

選択ソート

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

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

プログラミング例: 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 つのステップに分かれます。

（１）順序付けられていないシーケンスからヒープを構築する。

（２）最上位の要素を出力し、新たなヒープを形成する。

プログラミング例: 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)

要約する

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

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

• ソートするレコードの数 n

• 安定性の要件

• ストレージ構造

• 時間と補助空間の複雑さ

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

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

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

クイックソートは現在、比較ベースの内部ソートに最適な方法と考えられています。ソートされたキーワードがランダムに分散されている場合、クイックソートの平均時間は最短になります。 不安定

ヒープ ソートでは、クイック ソートよりも補助スペースが少なくて済み、クイック ソートで発生する可能性のある最悪のシナリオの影響を受けません。 しかし、まだ比較的不安定

マージソートは比較的安定していますが、一般的に使用することは推奨されません。実用性が低く、大量の補助スペースを占有する可能性があります。