任务是修改气泡排序,使其具有双向性。
这意味着"in“索引将首先从左到右携带最大的项,但是当它到达"out”时,它将从右向左反转和携带最小的项。
bubbleSort()方法正是在一个例子中给出的通常的方法。
我的代码在bidiBubbleSort().方法中
由于某种原因,当我运行程序时,它给了我一个被排序的输出,但不正确。
我用一支铅笔在一张纸上手工做了每一步,但我不知道我在忽略什么。
未分类:7 6 5 4 3 2
和
排序:6 4 2 1 3 5 7
class ArrayBub
{
private long[] a; // ref to array a
private int nElems; // number of data items
// --------------------------------------------------------------
public ArrayBub(int max) // constructor
{
a = new long[max]; // create the array
nElems = 0; // no items yet
}
// --------------------------------------------------------------
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
// --------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
// Beginning of my code -------------------------------------------------------
public void bidiBubbleSort()
{
int out, x, y;
int in = 0;
for(x=0, out=nElems-1; out>x; out--, x++) // outer loop (backward)
for(in=x; in<out+1; in++) // inner loop (forward)
if( in<out )
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
else // (in==out)
for(y=out-1; y>x; y--) // reverse
if( a[y] < a[y-1] )
swap(y, y-1);
}
// End of my code -------------------------------------------------------------
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--) // outer loop (backward)
for(in=0; in<out; in++) // inner loop (forward)
if( a[in] > a[in+1] ) // out of order?
swap(in, in+1); // swap them
} // end bubbleSort()
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
// --------------------------------------------------------------
} // end class ArrayBub
class BubbleSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // array size
ArrayBub arr; // reference to array
arr = new ArrayBub(maxSize); // create the array
arr.insert(7); // insert 7 items
arr.insert(6);
arr.insert(5);
arr.insert(4);
arr.insert(3);
arr.insert(2);
arr.insert(1);
arr.display(); // display items
arr.bidiBubbleSort(); // bidirectional bubble sort
arr.display(); // display them again
} // end main()
} // end class BubbleSortApp发布于 2014-10-05 07:39:20
双向气泡排序或混合排序的主要目的是解决未排序列表末尾的最低值(也称海龟)的问题,使其比传统的气泡排序更快地移到列表的开头。
牢记这一目标,您需要了解双向气泡排序的两端。从开始到结束的列表,结束开始的列表 pass。
您当前的实现似乎未能成功地调整常规的气泡排序。我的建议是忘记气泡排序和代码的实现,并考虑到上面提到的目标w.r.to冒泡排序。
首先,下面是一个提示:
动态地决定外部循环的退出,并设置一个条件来检查列表是否已经排序。不要像传统的气泡排序那样依赖外循环上的计数器。
如果您仍然无法解决这个问题,请浏览一下维基百科的文章,然后实现:sort。只有当你解决不了它的时候,才看它!
https://stackoverflow.com/questions/26199817
复制相似问题