How to master and use bubble sorting

This article mainly explains "how to master and use bubble sorting". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought. Let's study and learn how to master and use bubble sorting.

1. What is Bubble sorting

The bubble sorting algorithm needs to traverse the array several times, comparing consecutive adjacent elements in each iteration. If a pair of elements are arranged in descending order, swap their positions, otherwise they remain the same. As a result, smaller values float to the top like "bubbles", while larger values sink to the bottom, so this sorting method is called bubble sort (bubble sort) or sink sort (sinking sort).

After the first traversal, the last element becomes the largest element. After the second traversal, the penultimate element will be the second to last element. The whole process continues until all the elements are sorted.

two。 Graphical bubbling sort

After the first traversal, the largest number is already at the end of the array. Because the last number is already the maximum, there is no need to consider the last pair of elements.

After a second traversal, the last two numbers are sorted, so only the elements other than them need to be sorted.

Therefore, when doing the nth traversal, there is no need to consider the penultimate element, because they are already in order!

Bubble sort pseudo code:

For (int k = 1; k

< list.length; k++){ for(int j = 0; j < list.length-k; j++) { if(list[j] >

List [j + 1]) {swap (list [I], list [I + 1]);}

3. Improved bubble sorting

Notice that the above sort is actually not swapped many times, so we can improve the bubble sort a little bit:

Boolean nextPass = true; for (int k = 1; k

< list.length && nextPass; k++){ nextPass = false; for(int j = 0; j < list.length-k; j++) { if(list[j] >

List [j + 1]) {swap (list [I], list [I + 1]); nextPass = true;}

4. Bubble sorting time complexity

At best, the bubble sort only needs to be iterated once to determine that the array is sorted, and there is no need for the next traversal. Therefore, in the best case, the time complexity of bubble sorting is O (n).

In the worst case, bubbling sort needs to be repeated. So the total number of comparisons is: $(nmur1) + (nMu2) + (nMu3) +. + 3 + 2 + 1 = ({\ frac N2 ^ 2}-{\ frac N2}) = O (n ^ 2) $so, in the worst case, the time complexity of bubbling sorting is O (n ^ 2).

5. Attached function

Public static void bubbleSort (int [] list) {boolean nextPass = true; for (int k = 1; k)

< list.length && nextPass; k++){ nextPass = false; for(int j = 0; j < list.length-k; j++) { if(list[j] >

List [juni1]) {int tmp = list [j]; list [j] = list [juni1]; list [juni1] = tmp; nextPass = true } Thank you for your reading. the above is the content of "how to master and use bubble sorting". After the study of this article, I believe you have a deeper understanding of how to master and use bubble sorting. The specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!