1.1並べ替え——挿入:なぜ並べ替えを先に言うのか

ソートは興味深い問題ですが、なぜ多くのアルゴリズム書籍がソートを前にしているのか考えてみてください.ソートはアルゴリズムに関する多くの知識を引き出すことができるからだと思います.
ソートアルゴリズムに接触し始めると、一般的に最初のアルゴリズムと2番目のアルゴリズムは常にソートを挿入し、選択します.なぜなら、彼らの時間の複雑さは分析しやすいからだ.
では、まず挿入ソートを見てみましょう.
挿入ソート(InsertionSort)という名前が付けられたのは、アルゴリズムがこの要素に1つの要素を挿入するたびに前の適切な位置にあるからです.CLRSはトランプで整理した例を覚えていて、かわいいですね.
そこで、このアルゴリズムについて説明します.2番目の要素に対してInsertを行い、要素2が1番目より小さいかどうか、はい、1番目の前に挿入します.そうしないと、順序が変わりません.3番目の要素Insertに対して、2番目より小さいかどうかは、→2番目の前に挿入します.1つ目より小さいかどうかは、→1つ目を挿入する前に、順番に並べます;・・・;最後の要素にInsertをして、順番を決めます.
したがって、挿入ソートには、n番目の要素を挿入アルゴリズムするときに、その前のn-1要素がソートされているという特徴があります.では、Insertをするときは、目標要素が条件を満たしていない場合、私たちの判断はすぐに終了し、無駄なことを続けるべきではないことに注意する必要があります.
では、このアルゴリズムをc言語で実現します.

void InsertionSort( ElementType A[ ], int N)  //ElementType       ，  int，float ；N      
{
        int i, j;
        ElementType tmp;  //  tmp          ，       
        for( i = 1; i < N; ++i )
        {
                tmp = A[ i ];  
                for( j = i; j > 0 && tmp < A[ j - 1 ]; --j )  //  tmp          
                        A[ j - 1 ] = A[ j ];  //      （   tmp  ）      
                A[ j ] = tmp;  // tmp            
        }
}

注釈がある場合はよく読みますが、いくつかの機能を分析します.まず、

tmp < A[ j - 1 ]

ここでは比較を制御する要素をj,jはiから始まるので,最初からtmpとA[j−1]を比較させ,比較の条件に合えばA[j−1]を1桁後ろに移動し,jを1から減らす.tmpは常にA[j−1]と比較されるため、すなわち、最後にtmpが置かれる位置は条件を満たさないA[j−1]の前の位置である.これで巧みです.
BTWは、実はjを最初からi-1に等しくすることもできます.では、コードをどのように書き換えるか、自分で書いてください.検出が便利なので、私は言いません.(hint、CLRSを見ることができます.この本はこのような論理を使っていますが、実現する際に問題があります.jが-1に減る可能性があります.size_tでjのタイプを制御すると、エラーが発生します~)
2つのc/c++の文法についてお話ししましょう.1つ目はforサイクルです.皆さんご存知だと思いますが、forサイクルが条件を満たさなければ、終わるでしょう.では皆さんも忘れずに、

for( j = i; j > 0 && tmp < A[ j - 1 ]; --j )

tmp < A[ j - 1 ]が満たされていない場合、ループもすぐに終了します.j>0が満たされないまでstopだとは思わないでください.なぜかというと、選択ソートでは、満足しないですぐに止まるのではなく、プログラムがずっと判断する必要があるからです.
2つ目はこのElementTypeです.私たちが求めている配列がどんなタイプなのか分からないので、「要素タイプ」と呼ばれています.c++の実装では,このような「擬似コード」の書き方を避けるために,関数リロードの2つの手法がある.たとえば、int、doubleタイプの計算をアルゴリズムで満たすには、次のような宣言があります.

void InsertSort( int A[ ], int N );
void InsertSort( double A[ ], int N );

リロードを許可しないのは、戻りタイプの異なる関数のみであることに注意してください.
2つ目の方法は、汎用型です.汎用型はjavaに比べてちょっと難しいです.では、本問題の汎用性を簡単に理解しましょう.
c++汎用関数テンプレートの方法:

template  void InsertSort( T A[ ], int N )
{
     ...
    T tmp = A[ i ]; //   auto tmp = A [ i ];
    ...
}

そして直接呼び出せばいいです.コンパイラが自動的にインスタンス化するからです.
そしてその時間の複雑さを簡単に説明します.シーケンスがシーケンスである場合、内部サイクルは毎回1回のみ実行され、T(1)であるため、O()=T(n)*T(1)=O(n);最悪(逆シーケンス)の場合、内部はそれぞれ1,2,・・,n-1回比較・移動する必要があるので、O(n 2)回である.平均の場合、半分の順序が半分の逆順序であると仮定すると、依然としてO(n 2)である.
1つの挿入ソートでこれだけ書けるとは思っていませんでした・・・挿入、選択、ヒルソートを一緒に書こうと思っていたので、次回にしましょう~