这是我想出的：
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）。
可以使用队列和堆栈来实现自下而上的合并排序O（n log（n））。首先，所有元素都从堆栈中弹出到队列中（这使元素反向）。队列将被反向排序（反向比较的意义）。第一次合并传递从队列中弹出一个元素并将其推入堆栈，将queue.front（）与stack.top（）进行比较，将较小的元素弹出并推入队列，然后弹出并推入另一个元素，直到所有对元素重复合并，在队列中创建大小为2的排序运行。然后设置下一个遍历，循环循环以使所有偶数运行都反向（除非在末尾有一个单独的偶数运行且没有奇数运行合并，在这种情况下，它只是被复制而不是被反向）：甚至从队列运行都是推入堆栈，然后从堆栈中弹出并推入队列以将它们反转，奇数行从队列中弹出，然后推入队列以按顺序复制它们。对于其余的遍，通过从队列中弹出一个偶数运行并将其推入堆栈，在堆栈上“使其不可逆转”，将成对的运行合并，然后将stack.top（）的偶数运行与queue.front的奇数运行合并。 （），将合并的运行推回队列。一旦所有对被合并，运行大小将增加一倍，如果运行大小<queue.size（），则再次循环队列以撤消所有偶数运行，并重复合并过程。否则运行size> = queue.size（）并对队列进行排序（相反）。弹出反向排序的队列，并将其推入堆栈，以创建一个排序的堆栈。它在堆栈上，然后将stack.top（）上的偶数运行与queue.front（）上的奇数运行合并，将合并的运行推回队列。一旦所有对被合并，运行大小将增加一倍，如果运行大小<queue.size（），则再次循环队列以撤消所有偶数运行，并重复合并过程。否则运行size> = queue.size（）并对队列进行排序（相反）。弹出反向排序的队列，并将其推入堆栈，以创建一个排序的堆栈。它在堆栈上，然后将stack.top（）上的偶数运行与queue.front（）上的奇数运行合并，将合并的运行推回队列。一旦所有对被合并，运行大小将增加一倍，如果运行大小<queue.size（），则再次循环队列以撤消所有偶数运行，并重复合并过程。否则运行size> = queue.size（）并对队列进行排序（相反）。弹出反向排序的队列，并将其推入堆栈，以创建一个排序的堆栈。
我试图找出一种在合并过程中反转比较方式的方法，以避免在每次合并通过后都必须执行反向偶数运行循环，但这是一种递归模式，我无法弄清楚如何通过迭代进行复制。无论如何，更简单的反向平均运行方法似乎足够快。
在我的系统Intel 2600K 3.4 ghz，Visual Studio发行版上，此方法可以在大约2.8秒内对400万个伪随机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();
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句