java - 修改了冒泡排序，但无法正常工作

Question

任务是修改冒泡排序，使其具有双向性。

这意味着“in”索引将首先从左到右携带最大的项目，但当到达“out”时，它将反转并携带最小的项目项目从右到左。

bubbleSort() 方法只是示例中呈现的正常方式。

我的代码位于方法bidiBubbleSort()中。

由于某种原因，当我运行该程序时，它给了我一个已排序的输出，但不正确。

我用铅笔在一张纸上手动完成了每个步骤，但我不知道我忽略了什么。

Unsorted: 7 6 5 4 3 2 1

和

Sorted: 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

Answer 1

双向冒泡排序或鸡尾酒排序的主要目的是解决未排序列表末尾的最低值(又称海龟)问题，以便比传统冒泡排序更快地移动到列表的开头。

记住这个目标，您需要从两端理解双向冒泡排序。即，从列表末尾开始，每一次结束到列表开头。

您当前的实现似乎未能成功地调整传统的冒泡排序。我的建议是忘记冒泡排序的实现和代码，并牢记上述的冒泡排序目标。

首先，下面是一个提示:

Decide the exit of your outer loop dynamically with a condition to check if the list has been sorted or not. Do not rely on the counter on the outer loop like the conventional bubble sort does.

如果仍然无法解决，请查看维基百科文章，然后实现:http://en.wikipedia.org/wiki/Cocktail_sort 。 只有解决不了才看!