优化冒泡排序（Java）
我想知道如何优化冒泡排序，以便它忽略已经排序的元素，即使在第一次传递之后。
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[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; is_sorted = false; } } if(is_sorted) return; } }
谢谢你的时间！
首先，您有一个越界访问：
for(int j=0; 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[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依次之后。 标准冒泡排序将通过（几乎）整个arraysk次。
但是如果你记得你最后一次交换的地方，你知道在那个索引之后，顺序中有最大的元素，所以
public static void bubblesort(int[] a) { int lastSwap = a.length-1; for(int i=1; i 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; } }
将仅通过整个数组的一次传递对上述示例进行排序，其余的只传递（短）前缀。
当然，总的来说，这不会给你带来太大的影响，但是无论如何优化冒泡排序都是徒劳的。
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; iinput[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; }
你应该为内部循环使用变量“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);
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); }
我设计了一种方法，通过排除在先前循环中排序的数组的开头和结尾的部分来减少迭代次数。
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在之前的回答中所说， 对于较大的arrays ， 它并没有做太多。
在上面的例子中，数组在第3次传球后排序，但我们仍将继续第4次传球。 假设如果数组已经排序，则不会进行交换（因为相邻元素总是按顺序排列），但我们仍将继续传递，并且仍然会有（n-1）次传递。
如果我们可以识别出数组已经排序，那么我们应该停止执行更多的传递。 这是对原始冒泡排序算法的优化。
如果特定传递中没有交换，则表示数组已经排序，因此我们不应该执行进一步的传递。 为此，我们可以有一个标志变量，在每次传递之前设置为true，并在执行交换时设置为false。
void bubbleSort(int *arr, int n){ for(int i=0; iarray[j+1]) { flag = true; int temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } // No Swapping happened, array is sorted if(!flag){ return; }}}
public class Tester { static boolean bubbleFlag = true; public static void main(String[] args) { int array[] = new int[] { 1, 9, 2, 3, 4, 5, 6 }; bubbleSort(array); } private static void bubbleSort(int...array) { System.out.println("Before Sorting: " + Arrays.toString(array)); for (int i = 0; i < array.length - 1; i++) { if (i > 0) if (bubbleFlag) break; for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) array = swap(j, j + 1, array); System.out.println("Iteration " + i + " :" + Arrays.toString(array)); } bubbleFlag = true; } } private static int[] swap(int i1, int i2, int...is) { bubbleFlag = false; is[i1] = is[i1] + is[i2]; is[i2] = is[i1] - is[i2]; is[i1] = is[i1] - is[i2]; return is; } }
优化的冒泡排序，只有1个循环
/*Advanced BUBBLE SORT with ONE PASS*/ /*Authored by :: Brooks Tare AAU*/ public class Bubble { public int[] bubble(int b[]){ int temp,temp1; for(int i=0;ib[i+1] ){ ///swap(b[i],b[i+1]); temp=b[i]; b[i]=b[i+1]; b[i+1]=temp; /*Checking if there is any number(s) greater than the current number. If there is swap them.*/ while(i>0){ if(b[i]b[i-1]){i--;} } } else{continue;} } return b; } ///the following is a function to display the Array public void see(int []a){ for(int j=0;j