ソート要約の挿入

前言
1、挿入ソート(Insertion sort)の基本思想
1)ソートを挿入する基本思想:すべてのレコードの挿入が完了するまで、ソートされるレコードを1つずつキーワードサイズで前にソートされたサブファイルの適切な位置に挿入する.
2)挿入ソート方法の代表:直接挿入ソートとヒルソート
一、直接挿入ソート
1、並べ替えの基本思想を直接挿入する
配列R[1…n]にソートされたレコードが格納されているとする.初期時、R[1]は1つの秩序領域を形成し、無秩序領域はR[2.n]である.i=2からi=nまで順次R[i]を現在の秩序領域R[1…i-1]に挿入し、n個のレコードを含む秩序領域を生成する.
直接ソートを挿入する基本的な動作は、現在の無秩序領域の1番目の記録R[i]を秩序領域R[1...i-1]の適切な位置に挿入し、R[1...i]を新しい秩序領域にすることである.この方法は秩序領域を1レコード増加させるたびに,通常増分法と呼ばれるからである.
2、直接挿入ソートアルゴリズムの核心

は、挿入するデータR[2…n]を準備する.

は、条件を満たす場合に、挿入値テンソル空間(データ後方シフト)

である.

排出箇所に値

を挿入する.
3、直接挿入ソートアルゴリズムの実現

void InsertSort(int *arr,int len)

  
{

  
  int i,j;        // i        ，j  i     

  
  int curValue;      //   i      

  
  for (i=1;i<len;i++)    //     arr[1], arr[2], arr[len-1]

  
  {

  
    if (arr[i]<arr[i-1])//            

  
    {

  
      curValue = arr[i];      //           

  
      j = i-1;          //   i     

  
      do            

  
      {

  
        arr[j+1] = arr[j];    //      ，        

  
        j--;

  
      } while (curValue<arr[j]);  // 

  
      arr[j+1] = curValue;    //                  

  
    }

  
  }

  
}

  
4、    ソートアルゴリズムの    
    ソートは、その でソートされ、  しています.    ソートの       はO(n),       はO(n^2),       はO(n^2)であった.
 、ヒルソート(Shellsort)
1、ヒルソートの    
まずn  の  を  のインクリメンタルとして り,ファイルのすべての  をグループに ける.すべての  の  のレコードは じグループに  されます.まず、 グループ で    ソートを います. に、2  のインクリメンタルを  して、  したインクリメンタル、すなわち、すべてのレコードが じグループに  されて    ソートされるまで、  のグループおよびソートを り します.
まず、  する  のシーケンス  をいくつかのサブシーケンス(    からなる)に  して    ソートし、 に  を    してソートし、シーケンス  の  が   に   (  が   さい)されたときに、  の  を    ソートします.    ソートは、  が   に   されている  (  に い  )に  が いためです.
この  は   にパケット    である.
2、ヒルソートアルゴリズムの  
インクリメンタルdの  
    ソート
3.ヒルソートアルゴリズムの 
n=10の  49,38,65,97,26,13,27,49,55,4を にとると
  gap=10/2=5
49   38   65   97   26   13   27   49   55   4 
1A                             1B 
       2A                            2B 
             3A                            3B 
                   4A                             4B 
                          5A                            5B 
1 A,1 B,2 A,2 Bなどはパケットタグであり,  は じグループで,   はそのグループのいくつかの  であり, じグループのデータを      してソートする.すなわち、5つのグループ(49,13)(38,27)(65,49)(97,55)(26,4)に けられ、 グループがソートされると(13,49)(27,38)(49,65)(55,97)(4,26)、   じになる.
2  のgap=5/2=2
ソート 
13   27   49   55   4    49   38   65   97   26  
1A         1B         1C         1D         1E  
       2A         2B         2C         2D         2E  
3  のgap=2/2=1
4    26   13   27   38    49   49   55   97   65  
1A  1B   1C  1D   1E    1F   1G   1H   1I    1J  
4  のgap=1/2=0のソートが  すると、  が られます.
4   13   26   27   38    49   49   55   65   97  
4、ヒルソートアルゴリズムの  
void ShellSort(int a[], int n)

  
{

  
    int d;

  
    for (d=n/2; d>0; d=d/2)                //     

  
    {

  
        for (int i=d; i<n; i+=d)

  
        {

  
            if (a[i]<a[i-d])

  
            {

  
                int j = i-d;

  
                int temp = a[i];

  
                do 

  
                {

  
                    a[j+d] = a[j];

  
                    j = j-d;

  
                } while (temp<a[j]&&j>=0);

  
                a[j+d] = temp;

  
            }        

  
        }

  
    }

  
}
  
5、ヒルソートアルゴリズムの    
         ，             O(nlogn)，        O(n^S)(1<S<2).
  
 
  
  :http://blog.csdn.net/morewindows/article/details/6668714