Stack と Queue を使用して整数の配列をソートするメソッドを作成する必要があります。たとえば、[-1, 7, 0, 3, -2] -> [-2, -1, 0, 3, 7] を指定した場合。ソート方法を使用するだけなので、この質問を行う方法が完全にわかりませんが、この質問ではそれが許可されていません。スタックとキューでこれを行う方法を誰か説明できますか?
質問する
10619 次
4 に答える
9
多くの高速ソート アルゴリズム (mergesort や quicksort など)は、単一リンク リストをスタック (先頭に要素を追加することによって) またはキュー (要素を先頭に追加することによって) として効率的に扱うことができるという事実を利用して、リンク リストに効率的に実装できます。後ろ）。したがって、この問題を解決する 1 つの可能な方法は、これらの並べ替えアルゴリズムの 1 つを使用して、通常のシーケンスではなく連結リストを並べ替えているかのようにアプローチすることです。
たとえば、キューを使用してマージソートを実装する簡単な方法の 1 つを次に示します。sをソートするためにこれを書きましたIntegerが、これは他の型を処理するように簡単に拡張できます。
public void mergesort(Queue<Integer> sequence) {
/* Base case: Any 0- or 1-element sequence is trivially sorted. */
if (sequence.size() <= 1) return;
/* Otherwise, split the sequence in half. */
Queue<Integer> left = new LinkedList<Integer>(),
right = new LinkedList<Integer>();
while (!sequence.isEmpty()) {
left.add(sequence.remove());
if (!sequence.isEmpty()) {
right.add(sequence.remove());
}
}
/* Recursively sort both halves. */
mergesort(left);
mergesort(right);
/* Merge them back together. */
merge(left, right, sequence);
}
private void merge(Queue<Integer> one, Queue<Integer> two,
Queue<Integer> result) {
/* Keep choosing the smaller element. */
while (!one.isEmpty() && !two.isEmpty()) {
if (one.peek() < two.peek()) {
result.add(one.remove());
} else {
result.add(two.remove());
}
}
/* Add all elements from the second queue to the result. */
while (!one.isEmpty()) {
result.add(one.remove());
}
while (!two.isEmpty()) {
result.add(two.remove());
}
}
全体として、これは漸近的に最適な O(n log n) 時間で実行されます。
または、次に示すように、クイックソートを使用することもできます。
public void quicksort(Queue<Integer> sequence) {
/* Base case: Any 0- or 1-element sequence is trivially sorted. */
if (sequence.size() <= 1) return;
/* Choose the first element as the pivot (causes O(n^2) worst-case behavior,
* but for now should work out fine. Then, split the list into three groups,
* one of elements smaller than the pivot, one of elements equal to the
* pivot, and one of elements greater than the pivot.
*/
Queue<Integer> pivot = new LinkedList<Integer>(),
less = new LinkedList<Integer>(),
more = new LinkedList<Integer>();
/* Place the pivot into its list. */
pivot.add(sequence.remove());
/* Distribute elements into the queues. */
while (!sequence.isEmpty()) {
Integer elem = sequence.remove();
if (elem < pivot.peek()) less.add(elem);
else if (elem > pivot.peek()) more.add(elem);
else pivot.add(elem);
}
/* Sort the less and greater groups. */
quicksort(less);
quicksort(more);
/* Combine everything back together by writing out the smaller
* elements, then the equal elements, then the greater elements.
*/
while (!less.isEmpty()) result.add(less.remove());
while (!pivot.isEmpty()) result.add(pivot.remove());
while (!more.isEmpty()) result.add(more.remove());
}
これは、最良の場合は O(n log n) 時間、最悪の場合は O(n 2 ) 時間で実行されます。興味深い演習として、予想される O(n log n) ランタイムを取得するためにピボットをランダムに選択するようにしてみてください。:-)
まったく異なるアプローチでは、値がすべて整数であることがわかっているため、値に対して最下位桁の基数ソートを行うことを検討できます。
public void radixSort(Queue<Integer> sequence) {
/* Make queues for values with a 0 in the current position and values with a
* 1 in the current position. It's an optimization to put these out here;
* they honestly could be declared inside the loop below.
*/
Queue<Integer> zero = new LinkedList<Integer>(),
one = new LinkedList<Integer>();
/* We're going to need 32 rounds of this, since there are 32 bits in each
* integer.
*/
for (int i = 0; i < 32; i++) {
/* Distribute all elements from the input queue into the zero and one
* queue based on their bits.
*/
while (!sequence.isEmpty()) {
Integer curr = sequence.remove();
/* Determine whether the current bit of the number is 0 or 1 and
* place the element into the appropriate queue.
*/
if ((curr >>> i) % 2 == 0) {
zero.add(curr);
} else {
one.add(curr);
}
}
/* Combine the elements from the queues back together. As a quick
* note - if this is the 31st bit, we want to put back the 1 elements
* BEFORE the 0 elements, since the sign bit is reversed.
*/
if (i == 31) {
Queue<Integer> temp = zero;
zero = one;
one = temp;
}
while (!zero.isEmpty()) result.add(zero.remove());
while (!one.isEmpty()) result.add(one.remove());
}
}
これは時間 O(n log U) で実行されます。ここで、U は に格納できる最大値ですint。
もちろん、これらのアルゴリズムはすべて効率的でエレガントです。ただし、 bogosortのような遅くて洗練されていないソートを実行したい場合もあります。現在、bogosort の実装はやや困難です。これは、通常、入力シーケンスをシャッフルする必要があるためです。これは、配列で行う方がはるかに簡単です。ただし、次のようにキューのシャッフルをシミュレートできます。
- キューへのランダム インデックスを選択します。
- その多くの要素を循環します。
- その要素をキューから削除し、結果に追加します。
- 繰り返す。
これにより、O(n) ではなく O(n 2 ) の時間がかかり、これにより、bogosort の予想時間が O(n &mdot; n!) ではなく O(n 2 &mdot; n!)になるという不幸な副作用があります。しかし、それは私たちが支払わなければならない代償です。
public void bogosort(Queue<Integer> sequence, Random r) {
while (!isSorted(sequence)) {
permute(sequence, r);
}
}
/* Checking if a sequence is sorted is tricky because we have to destructively modify
* the queue. Our process will be to cycle the elements of the sequence making sure
* that each element is greater than or equal to the previous element.
*
* Because we are using bogosort, it's totally fine for us to destructively modify
* the queue as long as all elements that were in the original input queue end up
* in the resulting queue. We'll do this by cycling forward through the elements
* and stopping if we find something mismatched.
*/
private void isSorted(Queue<Integer> sequence) {
int last = Integer.MIN_VALUE;
for (int i = 0; i < sequence.size(); i++) {
int curr = sequence.remove();
sequence.add(curr);
if (curr < last) return false;
}
return true;
}
/* Randomly permutes the elements of the given queue. */
private void permute(Queue<Integer> sequence, Random r) {
/* Buffer queue to hold the result. */
Queue<Integer> result = new LinkedList<Integer>();
/* Continuously pick a random element and add it. */
while (!sequence.isEmpty()) {
/* Choose a random index and cycle forward that many times. */
int index = r.nextInt(sequence.size());
for (int i = 0; i < index; i++) {
sequence.add(sequence.remove());
}
/* Add the front element to the result. */
result.add(sequence.remove());
}
/* Transfer the permutation back into the sequence. */
while (!result.isEmpty()) sequence.add(result.remove());
}
お役に立てれば！
于 2013-06-21T20:03:30.140 に答える
4
単純に並べ替えるには、arrayを使用できますArrays.sort()。
特にキューのPriorityQueue場合、をソートするために必要なものですQueue。Java docsをご覧ください。
PriorityQueueメソッドを使用して値を挿入するadd()と、ソートされたものがQueue返されます。を使用してソート順を制御することもできますComparator。
于 2013-06-21T19:45:49.970 に答える
1
スタックとキューはデータ構造です。Stack は FILO で、Queue は FIFO です。これらのデータ構造がどのように機能するかを理解していれば、これを理解することができます。最終的には、データ構造としてスタックとキューを使用する必要があることを除いて、このタイプの問題に対して通常使用するのと同じロジックを使用できます。
Java でスタックを使用する 1 つの方法は、再帰的な方法で数値をソートすることです。Java には内部メモリ スタックがあるためです。
それが役立つことを願っています。
于 2013-06-21T19:46:24.643 に答える