Overview
Bubble sorting is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are incorrect. The work of visiting the sequence is repeated until the sequence has been sorted. The origin of this algorithm is because the smaller the element will slowly "float" to the beginning of the sequence via exchange.
To put it simply, it is:
Bubble sorting is more than larger characters sinking behind the array (can be understood as below), and smaller characters float in front (above).
Intuitive interpretation diagram:
step
Compare adjacent elements. If the first one is bigger than the second one, exchange them for the two.
Do the same work for each pair of adjacent elements, starting from the first pair to the last pair at the end. At this point, the last element should be the largest number.
Repeat the above steps for all elements except the last one.
Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers that need to be compared.
Example
Raw data:
3 5 2 6 2
The first round
Comparing 3 and 5, 5 is greater than 3, no exchange 3 5 2 6 2 Continue comparing 5 and 2, 5 is greater than 2, exchange position 3 2 5 6 2 Continue comparing 5 and 6, 6 is greater than 5, no exchange 3 2 5 6 2 Continue comparing 6 and 2, 6 is greater than 2, exchange position 3 2 5 2 66 sinks to the end, both 2 emerge upwards (front) respectively.
Round 2
Comparison 3 and 2, 3 is greater than 2, exchange position 2 3 5 2 6 Comparison 3 and 5, 5 is greater than 3, no exchange 2 3 5 2 6 Comparison 5 and 2, 5 is greater than 2, exchange position 2 3 2 5 6 No need to compare 5 and 6
The third round
Comparison 2 and 3, 3 is greater than 2, no need to exchange 2 3 2 5 6 Comparison 3 and 2, 3 is greater than 2, no need to compare the exchange position 2 2 3 5 6
Round 4
Compare 2 and 2 without exchange 2 2 3 5 6
Four rounds end
2 2 3 5 6
Code Implementation (Java)
package com.coder4j.main.arithmetic.sorting;public class Bubble { /** * bubble sort* * @param array * @return */ public static int[] sort(int[] array) { int temp; // The first layer loop shows the number of rounds compared, such as length elements, and the number of rounds compared is length-1 (no need to compare with yourself) for (int i = 0; i < array.length - 1; i++) { System.out.println("Thread" + (i + 1) + "Wheel Start"); // The second layer of loop, each adjacent two comparisons decreases once, and the number of times decreases as the number of rounds increases. Each round determines the largest one, and there is no need to compare the largest one for (int j = 0; j < array.length - 1 - i; j++) { if (array[j + 1] < array[j]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } System.out.println("Th" + (i + 1) + "Round,"Th" + (j + 1) + "Compare:"); for (int k : array) { System.out.print(k + " "); } System.out.println(); } System.out.println("Result:"); for (int k : array) { System.out.print(k + " "); } System.out.println(); } return array; } public static void main(String[] args) { int[] array = { 3, 5, 2, 6, 2 }; int[] sorted = sort(array); System.out.println("final result"); for (int i : sorted) { System.out.print(i + " "); } }}Test output results:
2 3 5 6 6 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 3 3 3 5 6 4 3 3 5 6 4 4 4 4 4 4 5 6 4 4 4 4 4 4 4 5 6 4 4 4 4 4 4 4 4 4 4 5 6 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 Final result 2 2 3 5 6
After testing, it is consistent with the results in the example.