Principle: Compare two adjacent elements and exchange elements with large values to the right end.
Idea: Compare two adjacent numbers in sequence, place the decimals in front and the large numbers in the back. That is, on the first trip: first compare the first and second numbers, put the decimal before and the big numbers after. Then compare the second number and the third number, put the decimal before and after the big number, continue like this until the last two numbers are compared, put the decimal before and after the big number. Repeat the first step until all sorting is complete.
For example: To sort the array: int[]arr={6,3,8,2,9,1};
First order:
First sort: 6 and 3 compare, 6 is greater than 3, swap position: 368291
Second sort: 6 and 8 compare, 6 is less than 8, no exchange position: 368291
The third order: 8 and 2 compare, 8 is greater than 2, swap position: 362891
Fourth order: 8 and 9 compare, 8 is less than 9, no exchange position: 362891
Fifth order: 9 and 1 compare: 9 is greater than 1, swap position: 362819
The first trip was compared in total 5 times, sorting results: 362819
---------------------------------------------------------------------
Second order:
First sorting: 3 and 6 compare, 3 is less than 6, no exchange position: 362819
Second sort: 6 and 2 compare, 6 is greater than 2, swap position: 326819
The third order: 6 and 8 compare, 6 is greater than 8, no exchange position: 326819
Fourth order: 8 and 1 compare, 8 is greater than 1, swap position: 326189
The second trip was compared in total, and the sorting result was: 326189
---------------------------------------------------------------------
The third order:
First sort: 3 and 2 compare, 3 is greater than 2, swap position: 236189
Second sort: 3 and 6 compare, 3 is less than 6, no exchange position: 236189
The third order: 6 and 1 compare, 6 is greater than 1, swap position: 231689
The second trip was compared in total, and the sorting result was: 231689
---------------------------------------------------------------------
The fourth order:
First sorting: 2 and 3 compare, 2 is less than 3, no exchange position: 231689
Second sort: 3 and 1 compare, 3 is greater than 1, swap position: 213689
The second trip was compared in total, and the sorting result was: 213689
---------------------------------------------------------------------
The fifth order:
First sort: 2 and 1 compare, 2 is greater than 1, swap position: 123689
The second trip was compared in total, and the sorting result was: 123689
---------------------------------------------------------------------
Final result: 123689
---------------------------------------------------------------------
From this we can see that N numbers need to be sorted, and N-1 times are sorted in total. The number of sorting times for each i-pass is (Ni), so you can use a double loop statement to control how many times the outer layer will control the number of times for each trip, that is,
for(int i=1;i<arr.length-1;i++){ for(int j=1;j<arr.length-1-i;j++){ //Swap position}Advantages of bubble sorting: Every time you sort, you will compare less, because every time you sort, you will find a larger value. As mentioned above: After the first comparison, the last number must be the largest number. When sorting the second time, you only need to compare other numbers other than the last number, and you can also find that the largest number is ranked after the number participating in the second comparison. When comparing the third time, you only need to compare other numbers other than the last two numbers, and so on... In other words, if you do not perform a comparison, each time you compare once, which reduces the amount of the algorithm to a certain extent.
In terms of time complexity:
1. If our data is in order, we only need to take a trip to complete the sorting. The required number of comparisons and record movements are both the minimum value, that is: Cmin=n-1;Mmin=0; Therefore, the best time complexity for bubble sorting is O(n).
2. If unfortunately our data is inverse order, n-1 ordering is required. Each order must be compared (1≤i≤n-1), and each comparison must be moved to the record three times to reach the exchange record position. In this case, the comparison and movement times both reach the maximum: the worst time complexity of bubble sort is: O(n2).
To sum up: The total average time complexity of bubble sort is: O(n2).
Code implementation:
/* * Bubble Sort */public class BubbleSort { public static void main(String[] args) { int[] arr={6,3,8,2,9,1}; System.out.println("The array before sorting is: "); for(int num:arr){ System.out.print(num+" "); } for(int i=1;i<arr.length;i++){//The outer loop controls the number of sorting times for(int j=1;j<arr.length-i;j++){//The inner loop controls how many times each time it is sorted if(arr[j-1]>arr[j]){ int temp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=temp; } } } System.out.println(); System.out.println("The sorted array is: "); for(int num:arr){ System.out.print(num+" "); } } }