1 
for (int p=1; p < a.size(); p++) {
    int tmp = a[p];
    for(j=p; j>0 && tmp < a[j-1]; j--) {
        a[j] = a[j-1];
    }
    a[j] = tmp;
}

挿入ソートの最悪のケースを理解するのに苦労しています。したがって、指定された配列は降順であり、昇順で並べ替えます。

外側のループは配列を通過します。したがって、実行されます（n回）。O(n) int tmp=a[p]---- このステートメントは n 回実行されます。O(n) 内側のループは (1+2+3+4+5+6+.... +n-1) 回実行されます。O(n^2) a[j]= tmp-------- このステートメントは n 回実行されます。の上）

挿入ソートの実行時間を見つけるために何をしたらよいかわかりません。できれば私の作品を修正してください。ありがとうございました。

4

2 に答える 2

2

これは、挿入ソートの2行の汎用C++11実装です。

template< typename ForwardIterator, typename Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type> >
void insertion_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare())
{
        for (auto it = first; it != last; ++it) {
                auto const insertion = std::upper_bound(first, it, *it, cmp);
                std::rotate(insertion, it, std::next(it));
        }
}

アルゴリズムは、要素の範囲（2つのイテレーターfirstとによって与えられるlast）と比較関数（デフォルトで、ポイントされる要素に組み込まれている可能性があります）を取りますoperator<。

メインループ（要素数が線形）は、サブインターバルを[first, it)並べ替えたままにし、次の要素を配置する場所の挿入ポイントを繰り返し検索します。これは、メインループに相当します。これは、二分探索（対数の複雑さ）で行われます。コードでは、逆線形検索を使用します（線形の複雑さはありますが、キャッシュ動作が向上する可能性があります）。

挿入ポイントを検出した後、2つの範囲とを回転させるだけです。これは、現在の要素を挿入ポイントにスワップすることを意味します。この回転は、これまでにソートされた要素の数に比例します。メインループにネストされているため、挿入ソートの全体的な複雑さは2次式です。。コードは、挿入ポイントのスワッピングと検索を統合しますが、それによって複雑さが変わることはありません。[insertion, it)[it, it+1)O(N^2)

入力範囲がすでにソートされている場合、挿入ポイントは常に、が指す要素と等しくなることに注意してください。これは、が何も交換する必要がないことをit意味します。std::rotate十分にスマートで最適化されたコンパイラは、その最適化を実行できるはずです。その場合、ソートされた範囲での挿入ソートは線形の複雑さを持ちます。

選択ソートへの同様の2行のアプローチがここに示されています。

于 2013-01-29T08:27:27.857 に答える
1

外側のループはn回実行されます。

内部ループの各実行は、0からp-1回の間のどこかで実行されます。ここで、pは0からnまで変化します。最悪の場合、p-1回実行されます。pが0からnまで変化する場合、平均してpはn/2です。したがって、内部ループの最悪の場合の複雑さは、O（p-1）= O（n / 2-1）= O（n）です。

ループを除いて、コードはすべてO（1）であるため（最も重要なのは、内側のループ内のコードが）、重要なのはループだけです。

O（n）* O（n）= O（n ^ 2）。

QED。

これはおおよそあなた自身が行った分析です。

于 2013-01-29T09:00:47.607 に答える