优化气泡排序（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最后条目排序，所以传统的冒泡排序使用

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之后。标准的Bubble排序将通过（几乎）整个阵列通过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排序无论如何都是徒劳的。

Answer 2

你应该在内部循环中使用一个变量“size”，并在每个循环中将其更改为最新的交换元素。这样，内部循环就会变成最新的“交换”元素，并传递其余未修剪的元素又名在他们的正确位置）。即

do { 
     int newsize =0; 
     for (int i = 1; i < size; i++) { 
      if (a[i - 1] > a[i]) { 
       int temp; 
       temp = a[i - 1]; 
       a[i - 1] = a[i]; 
       a[i] = temp; 
       newsize =i; 
      } 
     } 
     size = newsize; 
    } while (size > 0); 

Answer 3

public static Integer[] optimizedbubbleSort(Integer[] input){ 
    long startTime = System.nanoTime(); 
    boolean swapped = true; 
    for(int pass=input.length-1; pass>=0 && swapped; pass--){ 
     swapped = false; 
     for(int i=0; i<pass; i++){ 
      if(input[i]>input[i+1]){ 
       int temp = input[i]; 
       input[i] = input[i+1]; 
       input[i+1] = temp; 
       swapped = true; 
      } 
     } 
    } 
    System.out.println("Time taken for OPTIMIZED bubbleSort: "+(System.nanoTime() - startTime)); 
    return input; 
} 

Answer 4

public static void BubbleSorter(params int[] input){ 
     int newSize = input.Length-1, size = 0; 
     bool swap; 
     do 
     { 
      swap = false; 
      for (int j = 0; j < newSize; j++) 
      { 
       if (input[j] > input[j + 1]) 
       { 
        int temp = input[j + 1]; 
        input[j + 1] = input[j]; 
        input[j] = temp; 
        swap = true; 
        size = j; 
       } 
      } newSize = size; 
     } while (swap); 

     DisplayArrayElements(input); 
    } 

Answer 5

我设计，通过在已在先前的循环被命令数组的开始和结束部分除外减少迭代次数的方法。

static int[] BubbleSortOptimized(int arr[]) { 
    int start = 0, stop = arr.length - 1, control = 0; 
    boolean ordered, nsCaught; 
    while (true){ 
     ordered = true; 
     nsCaught = false; 
     for (int i = start; i < stop; i++) { 
      if (i > 1) { 
       if (!nsCaught && arr[i-2] > arr[i-1]){ 
        ordered = false; 
        start = i-2; 
        nsCaught = true; 
       } 
      } 
      if (arr[i] > arr[i+1]){ 
       int hold = arr[i]; 
       arr[i] = arr[i+1]; 
       arr[i+1] = hold; 
       control = i; 
      } 
     } 
     System.out.println(Arrays.toString(arr)); 
     if (ordered) return arr; 
     stop = control; 
    } 
} 

但作为@Daniel Fischer在更早的回答说，it doesn't do a lot with larger arrays.