ウィキペディアのソートアルゴリズムの「図解」が何を意味するのか、誰か説明してもらえますか? 私はそれらを理解できません。
バブルソート
挿入ソート
1 に答える
4
これらは、配列内のさまざまな要素の位置です (グレーのトーンが数値を示しているように見えます)。線は並べ替えのプロセスを示し、X 軸は時間であり、各時間ステップで 1 つまたは複数の要素が移動し、右側にそれらがトーンで並べ替えられていることがわかります。
ここでの違いは、バブル ソートが 1 つの要素を取り、隣接する要素の交換を開始することです (したがって、暗い灰色の要素が最後までゆっくりと伝播し、暗い灰色の要素に到達し、その要素を続行することがわかります)。
一方、挿入ソートは単一の要素を取り、それを挿入する場所を決定し、それに応じて残りの要素をシフトします。これは、すべて同時に移動する複数の平行な対角線で表されていることがわかります。
これはいい例ですが、アルゴリズムの説明を読んでみてください。それほど複雑ではありません。
これらの図から考えられるもう 1 つの利点は、配列を並べ替えるために必要なアクションの数を推測できることです。たとえそれが 1 つの例であり、必ずしも最悪のケースであるとは限りません。バブル ソートと挿入ソートはどちらも O(n^2) の大きさで、n は要素の数です。これは、n が大きくなるにつれて、非常に多くのアクション (スワップまたは挿入) を調べていることを意味します。これが、彼らがより複雑な他のソートアルゴリズムを思いついた理由です（O（n * logn）まで、一般的なケースではそれを打ち負かすことはできません）。たとえば、クイックソートを参照してください。また、ソートされた数値が上から制限されるなど、追加の制約に依存するアルゴリズム (ビンソート / 基数ソート)
于 2013-09-12T13:27:42.490 に答える