単純挿入ソート
読み：たんじゅんそうにゅうソート
外語：straight insertion sort

　ソートアルゴリズムの一つ。
　数列から最初の数字を1つずつ取り出して、すでにソート済みの数列の正しい位置に入れる。
　最悪計算量はO(n^2)であるが、すでに大部分がソート済である場合は計算量はO(n)に近づく。

単純挿入法の経過 4 8 7 1 2 6 9 10 3 5 開始 * 8 7 1 2 6 9 10 3 5 4 * * 7 1 2 6 9 10 3 5 4 8 * * * 1 2 6 9 10 3 5 4 7 8 * * * * 2 6 9 10 3 5 1 4 7 8 * * * * * 6 9 10 3 5 1 2 4 7 8 * * * * * * 9 10 3 5 1 2 4 6 7 8 * * * * * * * 10 3 5 1 2 4 6 7 8 9 * * * * * * * * 3 5 1 2 4 6 7 8 9 10 * * * * * * * * * 5 1 2 3 4 6 7 8 9 10 * * * * * * * * * * 1 2 3 4 5 6 7 8 9 10

再検索