挿入ソート最悪のケース

挿入ソートn^2が最悪の理由はなぜですか？バイナリ検索でnlognになることはできますか？ log（n）への位置検索を最小限に抑え、memmoveのような低レベル関数を使用してスワップを最小限に抑えますか？挿入ソート最悪のケース

2016-07-02 Taztingo

挿入の並べ替えがO（n^2）の理由は、最悪の場合、n個の項目をn回移動する必要があるためです。 'memmove'を使って項目を移動しても、時間の複雑さは変わりません。 – user3386109

これは、[\ [programmers se \]]（http://programmers.stackexchange.com）によく似ているので、この質問を議論の対象外とすることにしました。 – sjsam

質問に記述した変更を行うとそれはもはや挿入の並べ替えではありません。 –

-1

バイナリ検索でnlognになることはできますか？

バイナリ検索は、配列の最初の部分がソートされていてもソートされた配列にのみ

編集可能であるとしてあなたは、バイナリ検索を使用する最初の配列をソートする必要があります

。今の場合、あなたはlognステップで挿入する位置を見つけます。次に、そこに値を挿入する必要があります。そのためには、すべての要素を右に動かす必要があります。最悪の場合、n個のステップが必要です。

2016-07-02 04:38:51

挿入ソートは、配列のソートされた部分。一度に1つの要素。変更された挿入ソートは、新しい要素の挿入ポイントを見つけるためにリニアスキャンではなくバイナリ検索を使用することができます。これが@Taztingoの提案です。 –

答えて