Java classic algorithm bubble sort code sharing

Original title: Classic algorithm in Java: Bubble Sort (Bubble Sort)

What is bubble sort?

Bubble sort is a simple sorting algorithm that compares elements pairwise with each other in order. If the order is from large to small, then when two elements are compared with each other, the larger one will be ranked first; otherwise, the larger one will be ranked later. Bubble sorting is divided into sorting from large to small and sorting from small to large.

Principle: Compare two adjacent elements and swap the element with the larger value to the right end.

Idea: Compare two adjacent numbers in turn, put the decimal in front and the large number in the back. That is, in the first pass: first compare the first and second numbers, put the decimal first and the large number last. Then compare the second number and the third number, put the decimal in front and the large number in the back, and continue like this until comparing the last two numbers, put the decimal in front and the large number in the back. Repeat the first step until all sorting is completed.

Example: To sort the array: int[] arr={6,3,8,2,9,1};

The first sorting:

The first sorting: Comparing 6 and 3, 6 is greater than 3, swap positions: 3 6 8 2 9 1

Second sorting: Comparing 6 and 8, 6 is smaller than 8, do not exchange positions: 3 6 8 2 9 1

## The third sorting: 8# Compare ## and 2, 8 is greater than 2, exchange Position: 3 6 2 8 9 1

The fourth sorting:

8 and 9Compare, 8 is less than 9, no exchange of positions: 3 6 2 8 9 1## The fifth sorting: Comparison between

9

and 1: 9 is greater than 1, swap positions: 3 6 2 8 1 9 A total of

5

comparisons were made in the first trip, and the sorting results were: 3 6 2 8 1 9

-------------------------------------------------- -----------------------

Second sorting:

　　First Sorting: 3 and 6 are compared, 3 is less than 6 , do not exchange positions: 3 6 2 8 1 9

The second sorting: 6 and 2Compare, 6 is greater than 2, exchange positions: 3 2 6 8 1 9

The third sorting: 6 and 8 Comparison, 6 is greater than 8, without exchanging positions: 3 2 6 8 1 9

The fourth sorting: comparing 8 and 1, 8 is greater than 1, swap positions: 3 2 6 1 8 9

A total of 4 comparisons were made in the second pass, and the sorting results were: 3 2 6 1 8 9

---- -------------------------------------------------- ---------------

The third sorting:

The first sorting: 3 Compared with 2, 3 is greater than 2, exchange positions: 2 3 6 1 8 9

Second sorting: 3 and 6 Compare, 3 is less than 6, do not exchange positions: 2 3 6 1 8 9

The third sorting: comparing 6 and 1, 6 Greater than 1, exchange positions: 2 3 1 6 8 9

The second trip will be carried out in total 3 comparisons, sorting results: 2 3 1 6 8 9

------------ -------------------------------------------------- -------

##The fourth sorting:

The first sorting: 2 and 3 Compare, 2 is less than 3, do not exchange positions: 2 3 1 6 8 9

Second sorting: Comparison between 3 and 1 , 3 is greater than 1, swap positions: 2 1 3 6 8 9

A total of 2 comparisons were made in the second trip, sorting results: 2 1 3 6 8 9

------------------------------------------------ ---------------------

Fifth sorting:

First sorting: Comparing 2 and 1, 2 is greater than 1, exchange positions: 1 2 3 6 8 9

The second trip was conducted a total of 1 times Comparison, Sorting results: 1 2 3 6 8 9

------------------------ ----------------------------------------

Final result: 1 2 3 6 8 9

------------------- --------------------------------------------------

It can be seen that: N numbers need to be sorted, and a total of N-1 times of sorting are performed. iThe number of sorting times is (N-i) times, so you can use a double loop statement. The outer layer controls how many times the loop is, and the inner layer The layer controls the number of cycles of each pass, that is,

for(int i=1;i<arr.length;i++){

    for(int j=1;j<arr.length-i;j++){

    //交换位置

}

Advantages of bubble sorting: Each time a sort is performed, there will be one less comparison, because each time a sort is performed, Find a larger value. As in the above example: after the first comparison, the last number must be the largest number. During the second sorting, you only need to compare other numbers except the last number, and you can also find the largest number. The numbers are ranked behind the numbers participating in the second comparison. In the third comparison, only the other numbers except the last two numbers need to be compared, and so on... In other words, without a comparison, every time One less comparison per trip reduces the amount of algorithm to a certain extent.

In terms of time complexity:

　1. If our data is in correct order, we only need one trip to complete the sorting. The required number of comparisons and the number of record moves both reach the minimum value, that is: C_min=n-1;M_min=0; Therefore, bubble sort The best time complexity is O_(n).

2. If unfortunately our data is in reverse order, n-1 passes are required. Sort. Each sorting operation requires n-i comparisons(1≤i≤n-1), and each comparison must move the record three times to reach the exchange record position. In this case, the number of comparisons and moves reaches the maximum: The worst time complexity of bubble sort is: O_(n²).

To sum up: the total average time complexity of bubble sort is: O_{(n² )}.

Java Classic Algorithm Bubble Sort Code：

/*
 * 冒泡排序 */public class BubbleSort {
　　public static void main(String[] args) {
　　　　int[] arr={6,3,8,2,9,1};
　　　　System.out.println("排序前数组为：");
　　　　for(int num:arr){
　　　　　　System.out.print(num+" ");
　　　　}
　　　　for(int i=0;i<arr.length-1;i++){//外层循环控制排序趟数　　　　　　for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次　　　　　　　　if(arr[j]>arr[j+1]){
　　　　　　　　　　int temp=arr[j];
　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　arr[j+1]=temp;
　　　　　　　　}
　　　　　　}
　　　　} 
　　　　System.out.println();
　　　　System.out.println("排序后的数组为：");
 　　　　for(int num:arr){
 　　　　　　System.out.print(num+" ");
 　　　　} 
　　}
 }

More For more sharing about the classic Java algorithm bubble sort, please pay attention to the php Chinese website!