优化冒泡排序(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.

但是,在冒泡排序中,您知道在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;
  }
}

将仅通过整个数组的一次传递对上面的示例进行排序,其余的只传递(短)前缀.

当然,总的来说,这不会给你带来太大的影响,但是无论如何,优化冒泡排序是徒劳的.