Bubble sort

Concept

Bubble sort （Bubble Sort）, It's a kind of The field of computer science Simpler Sorting algorithm .

it Repeatedly Visited the element column to be sorted , Compare the two in turn adjacent The elements of , If the order （ : from large to small 、 First letter from Z To A） Mistakes are exchanged . The job of visiting an element is to do it repeatedly until no adjacent elements need to be exchanged , That is to say, the element column has been sorted .

The name of this algorithm comes from the fact that the smaller the elements, the more slowly “ floating ” Go to the top of the list （ Ascending or descending order ）, Just as the bubbles of carbon dioxide in carbonated drinks eventually rise to the top , So the name “ Bubble sort ”.

Algorithm principle

The principle of bubbling is as follows ： 

1. Compare adjacent elements . If the first one is bigger than the second one , Just swap them .

2. Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple . At this point , The last element should be the largest number . 

3. Repeat the above steps for all elements , Except for the last one .

4. Keep repeating the above steps for fewer and fewer elements each time , Until there's no pair of numbers to compare . 

flow chart ：

Time complexity

If the initial state of the file is in positive order , One scan to complete sorting . Comparison of required keywords   And record the number of moves   All reach the minimum value , therefore , The best time for bubble sorting is O(n).

The worst time complexity of bubble sorting is O（n²）.

Sum up , The total average time complexity of bubble sorting by O（n²）

Algorithm stability

Bubble sort is to move small elements forward or to move large elements back . Comparison is the comparison of two adjacent elements , The exchange also happens between these two elements . therefore , If two elements are equal , No more exchange ; If two equal elements are not adjacent , So even if we exchange the two in front of each other to make the two adjacent , It won't be exchanged at this time , So the order of the same elements hasn't changed , So bubble sort is a sort of Stable sequencing Algorithm .

Optimize

• Aiming at problems ：

After the order of the data is arranged , The bubbling algorithm will continue the next round of comparison , until arr.length-1 Time , The latter comparison is meaningless .

• programme ：

Set flag bit flag, If there is an exchange flag Set to true; If there is no exchange, set it to false.

So when a round of comparison is over, if flag Still false, namely ： There was no exchange in this round , The data has been sequenced , There's no need to go on .

Example ：

public static void BubbleSort1(int [] arr){
　
　
　   int temp;// Temporary variable 
　
　   boolean flag;// Whether to exchange the logo 
　
　   for(int i=0; i<arr.length-1; i++){   // Indicates the number of trips , altogether  arr.length-1  Time 
　
　
　       //  Each traversal flag bit must be set to false, To determine whether the elements behind the exchange 
　
　       flag = false;
　
　       
　
　       for(int j=arr.length-1; j>i; j--){ // Select the maximum value of this sort and move back 
　
　
　           if(arr[j] < arr[j-1]){
　
　               temp = arr[j];
　
　               arr[j] = arr[j-1];
　
　               arr[j-1] = temp;
　
　               flag = true;    // As long as there is an exchange ,flag Set as true
　
　           }
　
　       }
　
　       //  Judge whether the flag bit is false, If false, It indicates that the following elements have been ordered , Just directly return
　
　       if(!flag) break;
　
　   }
　
　}

Algorithm comparison ：

Sorting algorithm	Average time complexity
Bubble sort	O(n²)
Selection sort	O(n²)
Insertion sort	O(n²)
Shell Sort	O(n1.5)
Quick sort	O(N*logN)
Merge sort	O(N*logN)
Heap sort	O(N*logN)
Radix sorting	O(d(n+r))