1

一般的に、より良い方法は何ですか。コレクションにN個の要素を挿入してから並べ替えるか、挿入する前に要素の正しい場所を見つけて、その場所に正確に挿入します（N回繰り返します）。

4

4 に答える 4

6

これは、使用中のデータ構造とアプリケーションに大きく依存します。

配列に要素を挿入するには、以下のすべての要素を右にシフトする必要があり、その結果、挿入されることに注意してくださいO(n)。 ただし、バイナリ検索ツリー
では、への挿入は可能ですが、配列よりもキャッシュ効率が低いため、処理速度が低下します。O(logn)

一方、挿入してから並べ替えると、最後の要素が挿入されてから待ち時間O(nlogn)が長くなります[並べ替え]。
また、頻繁にクエリを実行するが、要素を追加することはめったにない場合は、並べ替えを頻繁に避けたい場合は、要素を順番に保持するのが簡単な方法です。

于 2012-08-31T17:21:42.337 に答える
1

入力を想定しない場合、ソートにはnlog（n）時間がかかります。要素の挿入にはO（n）時間がかかります（リンクリスト）。したがって、すべての挿入後の並べ替えが高速になります。

于 2012-08-31T17:19:18.320 に答える
1

これの方が良い

「コレクションにN個の要素を挿入してから並べ替える」

O(nlogn)アルゴリズムを使用して並べ替えることができるからです。これはどこに

「挿入する前に要素の正しい場所を見つけて、その場所に正確に挿入します（N回繰り返します）？」

の最悪の場合で知られている挿入ソートですO(n^2)。

とはいえ、挿入ソートはオンラインアルゴリズムです。つまり、並べ替えを開始するために事前にデータ全体を知る必要はありません。並行して実行されている他のプログラムによって生成されているデータについて考えてみます。ここで挿入ソートは理にかなっています。他のアプローチでは、データ全体を適切に配置する必要があります。

于 2012-08-31T17:35:14.583 に答える
0

データ構造によって異なります。ただし、挿入する前に適切な場所を見つけるには、要素を何らかの方法で並べ替える必要があります。これには、要素がデータ構造にすでに格納されている必要があります。達成しようとしていることに関する追加情報を提供できますか？

于 2012-08-31T17:21:31.340 に答える