直接挿入アルゴリズム

1アルゴリズムの原理
挿入アルゴリズムは、新しいデータを秩序化されたキューに挿入する毎に適切な位置に挿入するアルゴリズムである.アルゴリズムの詳細な手順は以下の通りです.無秩序列R 1,R 2,R 3,…,Rn(1)はまずR 1が秩序であると考えてR 2,R 3,...,Rnを順番にこの順序付けられたキューの適切な位置に挿入するために、外部サイクル(2)が必要です.Riを適切な位置に挿入する必要があります.私たちはRiを順次前のデータと比較し、比較するたびに前の列に挿入されるRiより大きなデータを後のビットに移動し、最初のRiより小さいデータRjを見つけて、Rjの後に挿入する必要があります.ここでは内部循環が必要です.
2コード実現

void insert_sort(int* array, int left, int right)
{
    int i = 0, j = 0;
    int tmp = 0;
    for (i = left + 1; i < = right; i++）
    {
        tmp = array[i];
        for (j = i; j > left; j--)
        {
            if (tmp < array[j-1])
            {
                array[j] = array[j-1];
            }
            else
            {
                array[j] = tmp;
                break;
            }
        }       
    }    
}

3性能分析
3.1時間複雑度
データの順序が正しい場合、実行効率が一番良く、挿入する度に前の要素を移動しなくてもいいです.時間の複雑さはO(N)です.
データが逆順序の場合、実行効率が最も悪く、挿入するたびに前の要素が後に移動し、時間の複雑さはO(N 2)である.
したがって、データは正の順序に近いほど、直接に並べ替えのアルゴリズム性能を挿入するのが良い.
3.2空間複雑度
直接的に並べ替えアルゴリズムを挿入することにより、並べ替え中に挿入する値を一時変数に記憶する必要があることが分かります.したがって、空間複雑度は1です.
3.3安定性
並べ替えを直接挿入する過程では,等しい数値要素の位置を変える必要がないので,安定したアルゴリズムである.