1

容量nn+mの 2 つの配列 (ソートされていない) があります。最初の配列にはn 個の要素があります。2 番目の配列にはm 個の要素があります (さらに、より多くの要素用にn 個の場所が予約されています)。

目標は、余分なスペースを使用せずに、2 つの配列をマージし、結果をソートされた方法で 2 番目の配列に格納することです。

現在、クイックソートを使用して両方の配列をソートしてから、マージソートを使用してそれらをマージしています。これを達成するためのより効率的な方法はありますか???

4

5 に答える 5

2

明らかに最善の方法は、N の内容を N+M 配列の空き領域にコピーし、N+M 配列をクイックソートすることです。

2 つのクイックソートを実行してからマージ ソートを実行すると、操作全体の効率が低下します。

長さ M の配列をソートする必要がある場合、それを 2 つの配列 M1 と M2 に分割し、それぞれをソートしてからマージソートしますか? いいえ。そうすると、クイックソートの各呼び出しで利用できる情報が制限され、プロセスが遅くなります。

では、なぜ 2 つの開始配列を別々にしておくのでしょうか?

于 2013-04-23T15:25:07.090 に答える
2

マージソートを調べることができます。

https://www.google.com/search?q=mergesort&ie=UTF-8&oe=UTF-8&hl=en&client=safari#itp=open0

または、サイズによっては、各配列でクイックソートを実行してから、マージソート手法 (またはマージしてからクイックソート) を使用してそれらをマージできます。

私はmergesortを使用します。基本的には、各配列を個別にソートしてから、それらを順番に並べることで機能します

マージソートでは O(nlogn) 、クイックソートでは O(nlogn) を見ていますが、クイックソートでは O(n^2) の最悪のケースが考えられます。

于 2013-04-23T11:48:14.580 に答える
0

小さい方の配列を N 配列、もう一方の配列を M 配列と呼びましょう。M 配列の要素は、最初は 0 から m-1 の位置にあると想定しています。好みの手法を使用して両方の配列を並べ替えます。これは、安定性や最悪の場合の動作の制限などの他の基準に依存する場合があります。

if min(N) > max(M)
   copy N's elements over starting at location m [O(n) time]   
else
   move M's elements to the end of the M array (last down to first) [O(m) time]   
   if min(M) > max(N)
      copy N's elements over starting at location 0 [O(n) time for the copy]
   else
      perform classic merge: min of remaining m's and n's gets migrated
      to next available space in M [O(min(m,n) time]

全体として、これは最初の並べ替え時間が支配的であり、マージ フェーズはすべて線形です。m を M 配列の末尾に移行すると、スペースの衝突がないことが保証されるため、仕様に従って追加のサイド ストレージは必要ありません。

于 2013-04-23T14:46:10.670 に答える