principle
Bubble sorting is probably an algorithm that all programmers can use and is also one of the most familiar algorithms.
Its ideas are not complicated:
Suppose that the array arr[] is now sorted, and it has n elements.
1. If n=1: Obviously, there is no need to queue up. (In fact, this discussion seems to be unnecessary)
2. If n>1:
(1) We start with the first element and compare every two adjacent elements. If the previous element is larger than the next one, then the former will definitely be ranked behind in the final result. So, we exchange these two elements. Then compare the next two adjacent elements. In this way, until the last pair of elements is compared, the first round of sorting is completed. It is certain that the last element must be the largest in the array (because the relatively large one is 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 arranged.
(3) So until there is only one element left, the element must be the smallest, and then our sorting can end. Apparently, n-1 sorting was performed.
In the above process, every time (or "wheel" is sorted, a number will slowly "float" from a certain position to the final position (draw a schematic diagram and draw the array vertically), just like bubbles, so it is called "bubble sorting method".
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++){ //Do not only n-1 ordering for(int j = 0;j < score.length - i - 1; j++){ //Sort the current unordered interval score[0......length-i-1] (the range of j is very critical, this range is really gradually narrowing) if(score[j] < score[j + 1]){ //Swap small values to the back int temp = score[j]; score[j] = score[j + 1]; score[j + 1] = temp; } } System.out.print("Th" + (i + 1) + "Sequence sorting result: "); for(int a = 0; a < score.length; a++){ System.out.print(score[a] + "/t"); } System.out.println(""); } System.out.print("final sorting result: "); for(int a = 0; a < score.length; a++){ System.out.print(score[a] + "/t"); } } }
Algorithm performance/complexity
We ignore the time when loop variables are automatically increased and initialized. First analyze the number of comparisons of the algorithm. It is easy to see that the above bubble sorting without any improvement will be performed in n-1 rounds regardless of the input data, and the number of times each round of sorting needs to be compared 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 make squares here, here, I use n^2 to represent squares, the same below)
Let’s take a look at the number of assignments. The assignment here refers to the exchange operation. For the above code, 1 exchange is equal to three assignments. Since not every time it is necessary to exchange, the number of assignment operations is related to the input data. In the best case, that is, when the order is in 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 average (or "completely random") distribution, then about half of the number of exchanges. From the above results, we can obtain the average case, with the number of assignments being 3/2 * (n^2)/2 = 3/4*(n^2).
In summary, in any case, the bubble sorting space complexity (extra space) is always O(1).
improve
The optimal time complexity is shown when the data is completely ordered, which is O(n). In other cases, it is almost always O(n^2). Therefore, the algorithm performs best when the data is basically ordered.
However, how can the above code have O(n) complexity? In fact, because the above focuses on basic ideas, 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) { // The length of each sort needs to be swap=false; for (int j = 0; j < i; ++j) { // From the first element to the i-th element 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 bubbleSortIn fact, because bubble sorting is hardly used in the case of large amounts of data, the added boolean variables when using small data will actually cause additional overhead. So I personally think that the improved algorithm above is only purely theoretical. Usually, just write the previous one by bubbling sorting.
Algorithm stability
It is easy to see that when neighboring elements are equal, we do not need to swap their positions, so bubble sort is a stable sort.
Algorithm applicable scenarios
The idea of bubble sorting is simple and the code is simple, which is especially suitable for sorting small data. However, due to the high complexity of the algorithm, it is not suitable for use when the data volume is large. If you must use it when there is more data, it is best to improve the algorithm, such as selecting the sorting method.