双向气泡排序

Question

我必须解决以下问题。所以最初我有一个冒泡排序，现在我修改它使其成为双向的。以下是我的解决方案。

public void bubbleSort() { 
    int temp; 
    int out; 
    int outNew = 0; 
    int in; 

    for (out = nElems - 1; out > outNew; out--) { 

     for (in = 0; in < out; in++) { 

      if (a[in] > a[in + 1]) { 
       temp = a[in + 1]; 
       a[in + 1] = a[in]; 
       a[in] = temp; 
      } 
     } 

     for (int j = in - 1; j > outNew; j--) { 

      if (a[j] < a[j - 1]) { 
       temp = a[j]; 
       a[j] = a[j - 1]; 
       a[j - 1] = temp; 
      } 

     } 

     outNew++; 

    } 

} 

当我打电话给我的冒泡排序来排序我创建的数组中的一些随机数似乎排序的很好。我的问题是所有的开发人员，无论我的解决方案是否满足上面提到的问题，以及我可以做些什么不同的事情来使此解决方案更有效（如果可能）。我很抱歉，如果这是一个小问题，我通常在这里寻找暗示和建议，而不是代码，因为它可以帮助我学得更好。我很感谢所有的答案，并欢迎任何建议。

Answer 1

您的第一个内部循环看起来效率不高，因为您的数组将在两端进行部分排序。第一轮（一次增加索引，一次减少索引）后，第一个和最后一个元素已经是正确的，因此不需要从索引0开始（并且任务/练习需要btw）。

以下ASCII技术表明，在其指数的算法应当在与9个元素的数组的例子上操作（包括与in+1和j-1达到指数;所述|之间的所有指数，应考虑）：

position: 0 1 2 3 4 5 6 7 8 
------------------------------------------------------------ 
      |     ->      | 
      |     <-     | 
       |    ->     | 
       |    <-    | 
        |   ->    | 
        |   <-  | 
         | ->  | 
         | <- | 

但是你的算法所做的是：

position: 0 1 2 3 4 5 6 7 8 
------------------------------------------------------------ 
      |      ->      | 
      |      <-      | 
      |      ->    | 
       |    <-    | 
      |      ->   | 
        |   <-   | 
      |      ->  | 
         |  <-  | 

你必须修复第一内的初始指数环。

Answer 2

总之，我不认为你能更有效地与我同时回答这个问题。这是非常明确的，你必须把你的物品搬到右边，直到你找到一个更小的物品，然后把它比你携带的最后一个小一点，然后拿起来。我认为普通的单向气泡排序并不会带来任何性能上的提升，但如果您打算使其成为双向排序，那么这就是做到这一点的方法。

你怎么知道？那么因为没有性能获得/恶化，左代码和右代码应该是完全对称的（因为它们在性能上是相同的）。就你而言，我可以说它看起来不错。

想想更深一点，可能会有一些轻微的优化来获得双向性，只是因为你得到了一个你刚才看到的物品，所以你知道你可以从它的初始位置左移，跳过右侧的阵列。但最终，它是微不足道的，它仍然是O（n²）表现，不管你如何切片。