アルゴリズム_挿入ソートの直接挿入ソート

ソートを挿入する基本的な考え方は、すべての要素を2つの区間に分割することです.ソート領域と無秩序領域は、最初は1つの要素しかありませんでした.その後、無秩序領域の要素を順番にソート領域に挿入します.この方法はインクリメンタル法と呼ばれ、挿入する要素ごとに1回の挿入と呼ばれます.
直接挿入ソートの基本構想
後ろから順番に挿入位置を検索し、検索しながら移動し、挿入要素より小さい最初の要素が見つかったら、後ろに挿入します.
アルゴリズム#アルゴリズム#

void insert_sort(RecType R[], int n)
{
    int i, j;
    RecType tmp;
    for (i=1; i= 0 && tmp.key < R[j].key);
        	R[j+1] = tmp;
        }
}

ぶんせき
時間の複雑さ

最良の時間複雑度:初期データシーケンスは正の順序であり、このときアルゴリズムは比較回数の無秩序領域のすべての要素を1回の比較のみを考慮し、移動する必要がないため、時間複雑度は

である.
O ( n ) O(n) O(n)

最悪時間複雑度:初期データシーケンスは逆シーケンスであり、このとき比較回数および移動回数はいずれも最大に達する.i番目の要素の挿入は、秩序領域[0,i-1]にi回の比較を比較する必要がある.比較するたびに移動する必要があり、2回の追加操作を加えるとi+2回の移動が必要となるため、時間的複雑度はΣ1 n−1(C i+M i)=Σ1 n−1(i+(i+2)=O(n 2)sum_1^{n-1} (C_i+M_i) =\sum _1^{n-1}(i + (i+2)) = O(n^2) 1∑n−1​(Ci​+Mi​)=1∑n−1​(i+(i+2))=O(n2)

平均時間複雑度:i番目の要素を秩序領域に挿入するには平均i/2回,平均移動回数i/2+2回が必要であるため,平均時間複雑度はΣ1 n−1(i 2+(i 2+2)=O(n 2)sum_1^{n−1}(frac i 2+(frac i 2+2))=O(n^2)1Σn−1(2 i+(2 i+2))=O(n 2)空間複雑度アルゴリズムで用いられる一時変数は問題規模に関係なく,時間複雑度O(1)O(1)安定性要素が最初のそれ以下の要素の後ろに挿入され,キーワードが同じ要素間の相対位置は変わらず,したがって、アルゴリズムの安定適用状況は、データ量が少なく、データシーケンスが基本的に秩序化する場合

である.