優化氣泡排序（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.