使用Java中的3个堆栈对未排序的数组进行排序
以下是我想要回答的问题
构造一种新的排序算法，它只使用标记为A、B和C的三个堆栈、一个名为x的“双”变量和任何辅助变量(如循环计数器)。您的算法假设堆栈A包含一组未排序的数据，到算法结束时，其中一个堆栈将包含按递增顺序排序的数据。
我正试图用Java为它找出算法，但我无法为自己的一生弄清楚它！你能帮忙吗？！
回答 4
Stack Overflow用户
发布于 2015-12-13 16:30:51
一个简单的程序可以从数组中获取值，然后将它们打印到命令控制台。
import java.util.*;
public class StackSort
{
static Stack<Double> A = new Stack<Double>();
public void createStackA()
{
double[] x = {-10,5, 2, 1, 9, 0, 10};
for (int i = 0; i < x.length; i++)
{
A.push(x[i]);
}
}
public void sortStackA(Stack<Double> C)
{
Stack<Double> B = new Stack<Double>();
while(!C.isEmpty())
{
double s1 = (double) C.pop();
while(!B.isEmpty() && (B.peek() > s1))
{
C.push(B.pop());
}
B.push(s1);
}
System.out.println(B);
}
public static void main(String[] args)
{
StackSort sS = new StackSort();
sS.createStackA();
sS.sortStackA(A);
}
}Stack Overflow用户
发布于 2015-12-14 18:30:45
如果有更快排序的奖励，使用3个堆栈，您可以实现自下而上的合并排序O(n log(n))。正如灰胡子指出的那样，多阶段自下而上的合并排序(一种面向磁带驱动器或其他顺序设备的方法)应该是最快的3堆栈排序。
简单的合并排序会将每次运行(初始大小== 1)从A移动到B和C，以交替的模式运行，偶数运行到B，奇数运行到C，然后双向合并B和C返回A，双运行大小，重复直到运行大小>=堆栈大小。聚相消除了移动/拆分步骤，但初始分配步骤除外，该步骤将部分元素从A移动到B和C。
设置初始降/升状态(反转比较的意义)，当堆栈上的运行大小由于虚拟元素而更改(+1或-1)时，跟踪会有些棘手。我使用一个由47个Fibonacci整数组成的表进行初始分发设置(句柄堆栈大小可达1/20亿元素)。堆栈大小在开始时是已知的，但这可以通过执行一个副本来生成(复制顺序并不重要，因为初始运行大小为1)。
N个元素的初始分布:假设fib(m+1) >n> fib(m)。n-fib(m)元素被移动到B. fib(m+1)-n元素被移动到C. n-fib(m)元素从A和B合并(推送)到C.在第一次合并后，C最终得到大小为2的n-fib(m)运行，而fib(m+1)-n运行的大小为1= fib(m-1)。B是空的。A的结果是(n) - ( fib(m+1) -n) - 2(n- fib(m) ) =2 fib(m) -fib(m+1)=fib(M)- fib(m- 1 ) = fib(m-2)，如果n= fib(m)，则fib(m-1)元素被移动到B中，将fib(m-2)元素留在A中。
Wiki文章还描述了类似于带有磁带驱动器的3堆栈排序的情况，但是在开始时没有提到如何分发虚拟运行(大小为0)的细节，但这可能包括在灰色胡子提到的55年前的出版物中。
排序
我编写了一个C++示例，但由于问题询问了C++ (下面的示例代码)，我将为C++示例提供一个指向zip的链接。C++示例使用每个数组(ppmrg3s.cpp)具有堆栈指针的数组，而不是堆栈类。zip还使用数组(ppmrg.cpp)进行了规则的多阶段合并排序。
http://rcgldr.net/misc/ppmrg.zip
示例java代码。在我的系统中，英特尔2600 K，3.4ghz，赢得了7 64位，它在大约4秒内达到1600万倍。
public class ppmrg3s {
static final int[] FIBTBL =
{ 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
267914296, 433494437, 701408733,1134903170,1836311903};
// return index of largest fib() <= n
static int flfib(int n)
{
int lo = 0;
int hi = 47;
while((hi - lo) > 1){
int i = (lo + hi)/2;
if(n < FIBTBL[i]){
hi = i;
continue;
}
if(n > FIBTBL[i]){
lo = i;
continue;
}
return i;
}
return lo;
}
// poly phase merge sort using 3 stacks
static void ppmrg3s(dstack a, dstack b, dstack c)
{
if(a.size() < 2)
return;
int ars = 1; // init run sizes
int brs = 1;
int asc = 0; // no size change
int bsc = 0;
int csc = 0;
int scv = 0-1; // size change value
boolean dsf; // == 1 if descending sequence
{ // block for local variable scope
int f = flfib(a.size()); // FIBTBL[f] >= size >= FIBTBL[f-1]
dsf = ((f%3) == 0); // init compare flag
if(FIBTBL[f] == a.size()){ // if exact fibonacci size,
for (int i = 0; i < FIBTBL[f - 1]; i++) { // move to b
b.push(a.pop());
}
} else { // else move to b, c
// update compare flag
dsf ^= 1 == ((a.size() - FIBTBL[f]) & 1);
// i = excess run count
int i = a.size() - FIBTBL[f];
// j = dummy run count
int j = FIBTBL[f + 1] - a.size();
// move excess elements to b
do{
b.push(a.pop());
}while(0 != --i);
// move dummy count elements to c
do{
c.push(a.pop());
}while(0 != --j);
csc = c.size();
}
} // end block scope
while(true){ // start merge pass
if(asc == a.size()){ // check for size count change
ars += scv; // (due to dummy run size == 0)
scv = 0-scv;
asc = 0;
csc = c.size();
}
if(bsc == b.size()){
brs += scv;
scv = 0-scv;
bsc = 0;
csc = c.size();
}
int arc = ars; // init run counters
int brc = brs;
while(true){ // start merge pair of runs
if(dsf ^ (a.peek() <= b.peek())){
c.push(a.pop()); // move a to c
if(--arc != 0) // if not end a
continue; // continue back to compare
do{ // else move rest of b run to c
c.push(b.pop());
}while(0 != --brc);
break; // and break
} else {
c.push(b.pop()); // move b to c
if(0 != --brc) // if not end b
continue; // continue back to compare
do{ // else move rest of a run to c
c.push(a.pop());
}while(0 != --arc);
break; // and break
}
} // end merge pair of runs
dsf ^= true; // toggle compare flag
if(b.empty()){ // if end b
if(a.empty()) // if end a, done
break;
b.swap(c); // swap b, c
brs += ars;
if (0 == asc)
bsc = csc;
} else { // else not end b
if(!a.empty()) // if not end a
continue; // continue back to merge pair
a.swap(c); // swap a, c
ars += brs;
if (0 == bsc)
asc = csc;
}
}
a.swap(c); // return sorted stack in a
}我创建了一个快速堆栈类，该类使用了一个固定的最大值双数组，其中包括一个交换函数成员：
class dstack{
double []ar; // array
int sz; // size
int sp; // stack pointer
public dstack(int sz){ // constructor with size
this.ar = new double[sz];
this.sz = sz;
this.sp = sz;
}
public void push(double d){
this.ar[--sp] = d;
}
public double pop(){
return this.ar[sp++];
}
public double peek(){
return this.ar[sp];
}
public boolean empty(){
return sp == sz;
}
public int size(){
return sz-sp;
}
public void swap(dstack othr){
double []tempar = othr.ar;
int tempsz = othr.sz;
int tempsp = othr.sp;
othr.ar = this.ar;
othr.sz = this.sz;
othr.sp = this.sp;
this.ar = tempar;
this.sz = tempsz;
this.sp = tempsp;
}
}测试程序。它使用随机整数(nextInt)，在a.push(.)期间被转换为双整数。这使得早期调试变得更容易。对于其他平台，或后续调试，对NUMELEM使用较小的数量，这是元素的数量。
static final int NUMELEM = 16*1024*1024;
public static void main(String[] args) {
dstack a = new dstack(NUMELEM);
dstack b = new dstack(NUMELEM);
dstack c = new dstack(NUMELEM);
Random r = new Random();
for(int i = 0; i < NUMELEM; i++){
a.push(r.nextInt(NUMELEM));
}
long bgn, end;
bgn = System.currentTimeMillis();
ppmrg3s(a, b, c);
end = System.currentTimeMillis();
double d;
d = a.pop();
while(!a.empty()){
if(d > a.peek()){
System.out.println("error");
break;
}
d = a.pop();
}
System.out.println("milliseconds");
System.out.println(end-bgn);
}Stack Overflow用户
发布于 2015-12-13 16:14:41
对于启动提示，请检查调车码算法，这是一种类似的方法，即操作符(即值)被推送到堆栈中，并弹出到另一个堆栈(即输出队列)，这取决于它们的相对优先级(即值)。
该算法有3个堆栈，a)输入队列(例如A)，b)运算符堆栈(例如B)和c)输出队列(例如C)，现在尝试将其转换为排序算法。
https://stackoverflow.com/questions/34253057
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号