【自考】データ構造知識まとめ【CH 7】

2781 ワード
試験を受ける
CH 7ソート
  1. 基本概念
ソートとは、オブジェクトのセットを所定の順序で並べ替えるプロセスであり、ソートは検索サービスであることが多い.
安定性:同じキー値の2つは、ソート前後の相対位置の変化を記録します.
直接挿入アルゴリズム,バブルソート,集計ソートなどの隣接する要素を比較するアルゴリズム.
隣接しない要素を比較するアルゴリズム、例えば、選択ソートの直接選択ソートとスタックソート、および高速ソート.
≪内部ソート|Internal Sort|emdw≫:ソートされるレコードは、コンピュータ・メモリに格納されているすべてのソートです.
外部ソート:ソートされるレコードの数が多く、メモリにすべてのレコードを格納できないため、外部ストレージにアクセスする必要があるソートプロセス
時間複雑度:キー値比較回数と記録移動回数で解析します.
基本秩序を記録する場合,挿入順序付けと交換順序付けが有効であり,直接挿入とバブル順序付けの時間的複雑さはいずれもO(n)であった.
並べ替えられるレコードの数が多い場合は、「並べ替え」を選択したほうが有効です.
    2. ソートの挿入
≪直接ソートの挿入|Insert Sort Direct|emdw≫:各レコードを順番にソートされたソート・テーブルに挿入します.最後まで行かないと、各キー値の最終位置を特定できません.
時間の複雑さ:
void StarightInsertSort(List R, int n)
{

  for (i=2;i<=n;i++)
  {
    R[0] = R[i];
    j = i-1;
    while (R[0].key < R[j].key)
    {
        R[j+1] = R[j];
        j--;
    }  
    R[j+1] = R[0];
   } // end of for

}

3.交換ソート
基本思想.
2つのレコードキー値のサイズを比較し、2つのレコードキー値のサイズが逆順序になった場合、この2つのレコードを交換します.
バブルソート
void BubbleSort(List R,int n)
{   int i,j,temp,endsort;
    for (i = 1; i<=n-1 ; i++)
    {  endsort = 0;
       for (j=1;j<=n-1;j++)
       {  
         if(R[j].key>R[j+1].key)
         {  temp = R[j];
            R[j] = R[j+1];
            R[j+1] = temp;
            endsort = 1;
         } // end of if
       } // end of for
      if (endsort == 0) break;
    } // end of for
}

クイックソート
//     
int QuickPartition(List R,int low,int high)
{  x = R[low];
   while(low < high)
   {
       while ((low < high) && R[high].key >= x.key)) high--;
       R[low] = R[high];
       while ((low < high) && R[low].key <= x.key)) low++;
       R[high] = R[low];
   }
   R[low] = x;
   return low;
}

//     
void QuickSort(List R,int low,int high)
{  if (low

4.ソートの選択
基本思想.
n−i+1個のレコードにおいて、キー値が最も小さいレコードを毎回選択し、i個目のレコードと交換する.
ちょくせつせんたく
void SelectSort(List R,int n)
{  int min,i,j;
   for (i = 1;i <= n-1; i++)
   {  min = i;
      for (j = i+1;j <= n; j++)
      { 
         if (R[j].key < R[min].key) min = j;
         if (min != i) swap(R[min],R[i]);  
      }
   }
}

ヒープのソート
スタックトップから下に調整するプロセスを「フィルタ」と呼びます.
時間の複雑さは全部でn個のノードがあり、フィルタリングするたびにlog 2(n)回まで比較し、O(n*log 2(n))
 
集計ソート
基本思想.
配列されるシーケンスは、いくつかの秩序化されたシーケンスから構成されることが要求される.
マージの方法は,各サブシーケンスの最初のレコードのキー値を比較し,最小の1つがソート後のシーケンスの最初のレコードのキー値である.このレコードを取り出し、各サブシーケンスの既存の1番目のレコードのキー値を比較し続けると、ソート後の2番目のレコードを見つけることができます.
空間的複雑さは、結果を格納するために、並べ替えられるレコードなどの数の配列bを使用するため、並べ替えソートを実現するには、記憶オーバーヘッドの2倍を追加する必要がある.
全部でlog 2(n)回あり,1回(n−区間数)回比較を行った.O(式階級より大きいまたは等しい階級)=O(n*log 2(n))
 
VBを使用して「華容道」問題を解く
【アルゴリズム】アルゴリズムの応用(三)