排序算法- java排序堆栈
以下是我想出的：
procedure sort(Stack S, Queue Q, sortedPosition)
if(sortedPosition==0)
// Sorting completed
return;
max = S.pop
currentPosition = 0;
while (!S.isEmpty()) do:
currentPosition = currentPosition + 1;
if(currentPosition < sortedPosition)
current = S.pop();
if(current > max)
Q.add(max);
max = current;
else
Q.add(current);
end if
end if
end while
S.push(max);
currentPosition--;
while (!Q.isEmpty()) do:
S.push(Q.remove());
end while
sort(S, Q, currentPosition);
end procedure有人能看看我是否做错了什么吗？此外，最坏的运行时间必须是O(n^2)。
回答 3
Stack Overflow用户
发布于 2015-12-08 15:47:52
可以使用队列和堆栈实现自下而上的合并排序O(n log(n))。首先，所有元素都从堆栈中弹出到队列中(这将反转元素)。队列将被反向排序(反转比较的意义)。第一次合并传递从队列中弹出一个元素并将其推入堆栈，将queue.front()与stack.top()进行比较，弹出并将较小的元素推入队列，然后弹出并推送另一个元素，直到所有元素合并为止，创建队列中大小为2的排序运行。然后，为了设置下一次运行，队列被循环以反转所有偶数运行(除非在结束时只有一个偶数运行，而没有奇怪的运行，在这种情况下，它只是被复制而不是反转)：从队列中的运行也被推到堆栈上，然后从堆栈弹出，然后被推到队列上来逆转它们，奇数运行从队列中弹出，然后按顺序推送到队列上复制它们。对于其余的传递，通过从队列中弹出偶数运行并将其推到堆栈上，“取消”堆栈上的偶数运行，然后在stack.top()处的偶数运行与queue.front()的奇数运行合并，将合并的运行合并到队列中。合并所有对后，运行大小加倍，如果运行大小< queue.size()，则会再次循环队列，以逆转所有偶数运行，并重复合并进程；否则，运行大小>= queue.size()和队列将被排序(反向)。反排序队列被弹出并推送到堆栈上，创建一个排序堆栈。
我试图找出一种方法来逆转合并期间的比较意义，以避免在每次合并通过之后进行反向甚至运行循环，但这是一种递归模式，我无法弄清楚如何使用迭代进行复制。简单的反向甚至运行方法似乎已经足够快了。
在我的系统中，Intel 2600K3.4GHz，Visual发布版，这种方法可以在2.8秒内对400万psuedo随机32位无符号整数进行排序。
升序堆栈的示例代码(降序的反向比较)。ll、rr和ee是伪索引，用于保持运行计数逻辑与数组/向量自下而上的合并排序相同。实际的合并将堆栈用于左/偶数运行，而队列的一部分用于右/奇数运行。
typedef unsigned int uint32_t;
void sqsort(std::stack <uint32_t> &s , std::queue <uint32_t> &q)
{
size_t n = s.size();
while(!s.empty()){ // pop/push s to q
q.push(s.top());
s.pop();
}
// merge sort usign stack and queue
size_t r = 1;
while(1){
size_t ee = 0; // pseudo end index
// merge pass
while(ee < n){
size_t ll = ee; // ll = pseudo start of left run
size_t rr = ll+r; // rr = pseudo start of right run
if(rr >= n){ // if only left run
while(ll++ < n){ // copy it and break
q.push(q.front());
q.pop();
}
break;
}
ee = rr+r; // ee = pseudo end of right run
if(ee > n)
ee = n;
// merge a pair of runs
// stack == left / even run
// queue == right / odd run
size_t m = rr - ll; // m = # elements in left run
while(m--){ // pop/push left run to stack
s.push(q.front());
q.pop();
}
m = ee - rr; // m = # elements in right run
while(1){
if(q.front() > s.top()){ // (reverse for descending)
q.push(q.front());
q.pop();
if(--m == 0){ // if end right run
while(!s.empty()){ // copy rest of left run
q.push(s.top());
s.pop();
}
break; // and break
}
} else {
q.push(s.top());
s.pop();
if(s.empty()){ // if end left run
while(m--){ // copy rest of right run
q.push(q.front());
q.pop();
}
break; // and break
}
}
} // end merge pair
} // end merge pass
r *= 2; // double run size
if(r >= n) // break if sort done
break;
// reverse left/even runs in q
ee = 0; // pseudo end index
while(ee < n){
size_t ll = ee; // ll = pseudo start of left run
size_t rr = ll+r; // rr = pseudo start of right run
if(rr >= n){ // if only left run
while(ll++ < n){ // copy it and break
q.push(q.front());
q.pop();
}
break;
}
ee = rr+r; // ee = pseudo end of right run
if(ee > n)
ee = n;
size_t m = rr - ll; // m = # elements in left run
while(m--){ // pop/push left run to s
s.push(q.front());
q.pop();
}
while(!s.empty()){ // pop/push s to q
q.push(s.top()); // (reverse left/even run)
s.pop();
}
m = ee - rr; // m = # elements in right run
while(m--){ // copy odd run to q
q.push(q.front());
q.pop();
}
} // end reverse left/even runs
} // end merge sort
while(!q.empty()){ // pop/push q to s
s.push(q.front());
q.pop();
}
}Stack Overflow用户
发布于 2015-12-08 09:15:54
这个问题很好。和我亲自检查了您的解决方案，它进入了无限循环，但是您的方法非常好。我稍微修改了一下你使用的逻辑。我尽量保留您的方法，。
我更改的逻辑是，首先将所有堆栈元素复制到队列中。然后，我使用我的登录来过滤队列，并将最高的元素逐一插入到堆栈中。一旦一个元素(按排序顺序)被推到堆栈中，相应的元素就会从队列中删除。
--请检查下面的解决方案--我是在java上做的。我希望它能帮到你..。
您必须(第一次)使用参数i调用排序方法。一个空队列，和iii.the no of element (堆栈的大小)..
Stack sort(Stack<Integer> s,Queue<Integer> q,int length)
{
if(length==0)
{
return s;
}
if(q.isEmpty())
{
while(!s.empty())
{
q.add(s.pop());
}
}
int stckElement;
int qElement;
s.push(q.remove());
int count=0;
while(count<length-1)
{
stckElement=s.pop();
qElement=q.remove();
if(stckElement<qElement)
{
s.push(qElement);
q.add(stckElement);
count=0;
}else
{
s.push(stckElement);
q.add(qElement);
count++;
}
}
length--;
return sort(s,q,length);
}Stack Overflow用户
发布于 2015-12-08 18:04:33
如果您在任何时候使用小于堆栈中元素数的sortedPosition调用该过程，则算法包含一个无穷循环，因为:在与sortedPosition相等的次数增加currentPosition之后，您将无法到达sortedPosition，然后您将违反if条件，堆栈不为空，然后您将继续增加currentPositionm，这是肯定的。
在while之后，您应该设置sortedPosition--;而不是currentPosition--;，然后为sortedPosition调用sort而不是currentPosition，在第一个调用中，它应该等于元素的数量。
正确的实现应该是：
procedure sort(Stack S, Queue Q, sortedPosition)
if(sortedPosition==0)
// Sorting completed
return;
max = S.pop
currentPosition = 0;
while (currentPosition < sortedPosition) do:
if(currentPosition < sortedPosition)
current = S.pop();
if(current > max)
Q.add(max);
max = current;
else
Q.add(current);
end if
end if
currentPosition = currentPosition + 1;
end while
S.push(max);
sortedPosition--;
while (!Q.isEmpty()) do:
S.push(Q.remove());
end while
sort(S, Q, sortedPosition);
end procedurehttps://stackoverflow.com/questions/34148431
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号