任務是修改氣泡排序以便它是雙向的。修改過的氣泡排序,但無法正常工作
這意味着「in
」索引將首先從左到右攜帶最大的項目,但是當它到達「out
」時,它將反轉並從右向左運送最小的項目。
bubbleSort()
方法只是它在示例中呈現的正常方式。
我的代碼是在方法bidiBubbleSort()
。
由於某些原因,當我運行該程序時,它給了我一個排序的輸出,但不正確。
我用鉛筆手動做了一張紙上的每一步,但我不知道我在忽略什麼。
未排序:7 6 5 4 3 2 1
和
排列: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