优化的冒泡排序（Java）

Question

我想知道还有什么可以优化冒泡排序的方法，以便即使在第一次通过之后也可以忽略已经排序的元素。

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**]

我们观察到[4,5,6]已经按顺序排列，如何修改我的代码，以便在下一遍中忽略这3个元素？（这意味着排序会更有效？）您是否建议使用递归方法？

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

谢谢你的时间！

Answer 1

首先，您具有越界访问权限：

    for(int j=0; j<a.length; j++) {
      if(a[j] > a[j+1]) {

因为j == a.length-1，所以循环条件应该是j < a.length-1。

但是，在Bubble排序中，您知道经过k传递后，最大的k元素将在k数组的最后一个条目中排序，因此常规的Bubble排序使用

public static void bubblesort(int[] a) {
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;

    for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
      }
    }

    if(is_sorted) return;
  }
}

现在，当数组具有长排序的最大元素尾部时，这仍然会进行很多不必要的迭代，比如说您k,k-1,...,1作为第一个k元素，然后k+1是100000000按顺序。标准的冒泡排序将k通过（几乎）整个数组传递时间。

但是，如果您还记得上一次交换的位置，您会知道在该索引之后，顺序是最大的元素，因此

public static void bubblesort(int[] a) {
  int lastSwap = a.length-1;
  for(int i=1; i<a.length; i++) {
    boolean is_sorted = true;
    int currentSwap = -1;

    for(int j=0; j < lastSwap; j++) {
      if(a[j] > a[j+1]) {
         int temp = a[j];
         a[j] = a[j+1];
         a[j+1] = temp;
         is_sorted = false;
         currentSwap = j;
      }
    }

    if(is_sorted) return;
    lastSwap = currentSwap;
  }
}

将仅对整个数组进行一次遍历，对上面的示例进行排序，而其余遍历仅对（短）前缀进行遍历。

当然，总的来说，买不到什么，但是优化Bubble排序却是徒劳无益的。