アルゴリズム----挿入順序(insert sort)

並べ替えを挿入すると、すべての要素が並べ替えを完了するまで、要素を選択するたびに並べ替えられたサブアレイに挿入します.
アルゴリズムの実装:

void sort::insert_sort(int* a, const int n)
{
	for(int i=1; i0 && a[j] < a[j-1]; j--)
		{
			swap(a,j,j-1);
		}
	}
}

上記アルゴリズムの時間複雑度はO(N^2)である.しかし、挿入順序付けのアルゴリズム性能は、順序付けされた配列に関係しており、配列が順序付けされている場合は、線形時間内に完了することができ、配列が逆順である場合は、O(N^2)の時間が必要となります.したがって、並べ替えアルゴリズムを挿入する時間の複雑さはN〜N^2の間にある.配列サイズが小さい場合や、複数の局所秩序のサブアレイがある場合、アルゴリズムの実行速度はより速くなります.