优化冒泡排序 (Java)

Optimized Bubble Sort (Java)

提问by kent

I would like to know how else I can optimize bubble sort so that it overlooks elements that have already been sorted, even after the first pass.

我想知道我还能如何优化冒泡排序，以便它忽略已经排序的元素，即使在第一遍之后也是如此。

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

We observe that [4,5,6] are already in sorted order, how can modify my code so that it overlooks this 3 elements in the next pass? (which means the sort would be more efficient?) Do you suggest a recursive method?

我们观察到 [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;
  }
}

Thanks for your time!

谢谢你的时间！

采纳答案by Daniel Fischer

First of all, you have an out-of-bounds access:

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

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

for j == a.length-1, so the loop condition should rather be j < a.length-1.

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

But, in Bubble sort, you know that after kpasses, the largest kelements are sorted at the klast entries of the array, so the conventional Bubble sort uses

但是，在冒泡排序中，你知道在遍历之后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;
  }
}

Now, that would still do a lot of unnecessary iterations when the array has a long sorted tail of largest elements, say you have k,k-1,...,1as the first kelements and k+1to 100000000in order after that. The standard Bubble sort will pass ktimes through (almost) the entire array.

现在，仍然会做很多不必要的迭代当阵列具有最大元素的长尾巴排序，说你k,k-1,...,1作为第一个k元素，并k+1以100000000在后的顺序。标准冒泡排序将k通过（几乎）整个数组传递时间。

But if you remember where you made your last swap, you know that after that index, there are the largest elements in order, so

但是如果你记得上次交换的位置，你就会知道在那个索引之后，有最大的元素按顺序排列，所以

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;
  }
}

would sort the above example with only one pass through the entire array, and the remaining passes only through a (short) prefix.

将对上面的例子进行排序，只通过整个数组一次，其余的只通过一个（短）前缀。

Of course, in general, that won't buy you much, but then optimising a Bubble sort is a rather futile exercise anyway.

当然，一般来说，这不会给你带来太多好处，但是无论如何优化冒泡排序是一个相当徒劳的练习。

回答by Panos Gr

you should use a variable "size" for the inner loop and change it to the latest swapped element in each cycle.This way your inner loop goes up to the latest "swapped" element and passes the rest that are unswapped (aka in their correctplace). i.e

你应该为内循环使用一个变量“大小”，并在每个循环中将其更改为最新的交换元素。这样你的内循环就会上升到最新的“交换”元素并传递其余的未交换元素（也就是在它们的正确位置）。IE

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);

回答by Sharath

 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;
}

回答by Dakshitha Mevan Dias

    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);
    }

回答by kbluue

I devised a method that reduces the number of iterations by excluding parts at the beginning and end of the array that have been ordered in previous loops.

我设计了一种方法，通过排除在先前循环中已排序的数组开头和结尾的部分来减少迭代次数。

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;
    }
}

But as @Daniel Fischersaid in an earlier answer, it doesn't do a lot with larger arrays.

但正如@Daniel Fischer在较早的回答中所说的那样，它对较大的数组没有多大作用。

回答by Chamila Maddumage

In the above example, the array got sorted after 3rd pass, but we will still continue with the 4th, 5th pass. Suppose if the array is already sorted, then there will be no swapping (because adjacent elements are always in order), but still we will continue with the passes and there will still be (n-1) passes.

在上面的例子中，数组在第 3 次通过后排序，但我们仍将继续第 4、5 次通过。假设如果数组已经排序，那么不会有交换（因为相邻元素总是按顺序排列），但我们仍然会继续传递，并且仍然会有 (n-1) 次传递。

If we can identify, that the array is sorted, then we should stop execution of further passes. This is the optimization over the original bubble sort algorithm.

如果我们可以确定数组已排序，那么我们应该停止执行进一步的传递。这是对原始冒泡排序算法的优化。

If there is no swapping in a particular pass, it means the array has become sorted, so we should not perform the further passes. For this we can have a flag variable which is set to true before each pass and is made false when a swapping is performed.

如果在特定的传递中没有交换，则意味着数组已排序，因此我们不应执行进一步的传递。为此，我们可以有一个标志变量，它在每次传递之前设置为 true，并在执行交换时设置为 false。

void bubbleSort(int *arr, int n){
for(int i=0; i<n; i++)
{  
  bool flag = false;
   for(int j=0; j<n-i-1; j++)
   {
      if(array[j]>array[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; 
  }}}

回答by Ahmed meeran

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;
    }
}

回答by Brook tare

Optimized bubble sort with just 1 for Loop

优化的冒泡排序，只有 1 个 for 循环

/*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;i<b.length-1;i++){

            if(b[i]>b[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]){
                    ///swap(b[i]<b[i-1])

                        temp1=b[i];
                        b[i]=b[i-1];
                        b[i-1]=temp1;
                        i--;
                    }
                    else 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<a.length;j++){
                System.out.print(a[j]+",");
            }
        }



    public static void main(String []args){
        ///You can change the Array to your preference.. u can even make it dynamic 

        int b[]={5,1,4,2,0,3}; 
        int v[]=new int[100]; 
        Bubble br=new Bubble();
        v=br.bubble(b);
        br.see(v);

    }
}

回答by Nishant Ingle

I think this is what you need. The key is to consider the array only till the index where last swap occured(newn).

我认为这就是你所需要的。关键是只考虑数组直到最后一次交换发生的索引（newn）。

public static void bubblesort(int[] a) {
  int i, n, newn;
  n = a.length;

  while (n > 0) {
      newn = 0;
      for (i = 1; i < n; i++) {
          if (a[i - 1] > a[i]) {
              temp = a[i];
              a[i] = a[i - 1];
              a[i - 1] = temp;
              newn = i;
          }
      }
      n = newn;
    }

    return a;
}

回答by M Peeran

Here is the simplest, best and optimal Bubble Sort Algorithm using a while loop. It sorts the numbers in the given array form left to right in ascending order. It is very simple to understand and easy to implement.

这是使用 while 循环的最简单、最好和最优的冒泡排序算法。它按升序从左到右对给定数组形式中的数字进行排序。它非常易于理解且易于实现。

private static int[] bubbleSort(int[] array) {

        int length = array.length - 1;
        int index = 0;

        while ( index < length) {

            if (array[index] > array[index + 1]) {
                swap(array, index, index + 1);
            }
            index++;

            if (index == length) {
                index = 0;
                length--;
            }
        }
        return array;
    }

    private static void swap(int[] array, int index1, int index2) {

        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }