Java implementation of bubble sort algorithm and its simple optimization example

Principle

Bubble sorting is probably an algorithm that all programmers will use, and it is also one of the most familiar algorithms.
The idea is not complicated:
Suppose now we want to sort the array arr[], which has n elements.
1. If n=1: Obviously there is no need to arrange. (In fact, this discussion seems unnecessary)
2. If n>1:
(1) We start from the first element and compare every two adjacent elements. If the previous element is better than the following element Big, then the former will definitely be ranked behind in the final result. So, we swap these two elements. Then compare the next two adjacent elements. This continues until the last pair of elements is compared, and the first round of sorting is completed. You can be sure that the last element must be the largest in the array (because the relatively large ones are placed at the back every time).
(2) Repeat the above process, this time we don’t need to consider the last one because it is already lined up.
(3) This is done until there is only one element left. This element must be the smallest, then our sorting can be completed. Obviously, n-1 sorting takes place.
In the above process, each time (or called "round") sorting, a number will slowly "float" from a certain position to the final position (draw a schematic diagram and draw the array vertically to see this. ), just like bubbles, so it is called "bubble sort".

Code implementation:

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print("第" + (i + 1) + "次排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

Algorithm performance/complexity
We ignore the time for loop variable increment and initialization. First analyze the number of comparisons of the algorithm. It is easy to see that the above bubble sort without any improvement will perform n-1 rounds of sorting regardless of the input data, and the number of comparisons required for each round of sorting decreases from n-1 to 0. Then, the total number of comparisons is (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2. (Since I don’t know how to calculate the square here, here, I use n^2 to represent the square, the same below)
Let’s look at the number of assignments. The assignment here refers to the exchange operation. For the above code, one exchange is equal to three assignments. Since swapping is not necessary every time, the number of assignment operations is related to the input data. In the best case, that is, when it is ordered from the beginning, the number of assignments is 0. In the worst case, the number of assignments is (n-1)n/2. Assuming that the input data is evenly (or "completely random") distributed, then there are approximately half the number of exchanges as there are comparisons. From the above results, we can get that under the average case, the number of assignments is 3/2 * (n^2)/2 = 3/4*(n^2).
To sum up, no matter what kind of In this case, the space complexity (extra space) of bubble sort is always O(1).

Improvement
The optimal time complexity is O(n) when the data is completely ordered. Otherwise, it's almost always O(n^2). Therefore, the algorithm performs best when the data is basically ordered.
But, how can the above code have O(n) complexity? In fact, because the above focuses on the basic idea, it is only the simplest case. To make the algorithm have O(n) complexity in the best case, some improvements need to be made. The improved code is:

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

Actually, since bubble sorting is almost never used when using large amounts of data, adding Boolean variables when using small data will cause additional overhead. Therefore, I personally think that the improved algorithm above is purely theoretical. Usually, for bubble sorting, just write the former one.

Algorithm stability
It is easy to see that when adjacent elements are equal, we do not need to exchange their positions, so bubble sorting is a stable sorting.

Applicable Scenarios of the Algorithm
Bubble sorting has a simple idea and simple code, and is especially suitable for sorting small data. However, due to the high complexity of the algorithm, it is not suitable for use when the amount of data is large. If it must be used when there is a lot of data, it is best to improve the algorithm, such as selection sorting.

For more Java implementation of the bubble sort algorithm and its simple optimization examples, please pay attention to the PHP Chinese website!