The profile

Bubbling sort gets its name from the fact that larger elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top. Bubble sort is the entry level sorting algorithm of eight kinds, and it is also a classical sorting algorithm. This system introduces the principle and implementation of bubble sort.

The principle of

Loop through two adjacent elements of the array, moving the larger number to the end, and the largest number is moved to the end after a sort. Then eliminate the last maximum number, continue the loop to move the maximum number to the end, and finally keep the array in order.

A trip to the sorting

Int n[] = {6, 5, 2, 7, 1}

  • The first time 6 and 5 are compared, the larger number 6 is swapped with 5;
  • The second time 6 and 2 are compared, the larger number 6 continues to swap with 2;
  • The third time 6 and 7 are compared, the larger number 7 does not need to be swapped;
  • The fourth time 7 and 1 are compared, the larger numbers 7 and 1 are swapped;

The largest number in the array, 7, is at the bottom of the array after a sorting

Multiple sort control

By controlling the subscript size of the array, the number of arrays that need to be sorted is reduced by one in each cycle, so that after removing the current largest element after a sort, the comparison and exchange will continue to move the largest digit to the last digit successively:

  • The first sort moves the largest number 7 to the bottom;
  • The second sort moves the largest number before 7, 6, to the second from last;
  • The third sort moves the largest number before 6, 5, to the third from the bottom;
  • The fourth sort moves the largest number before 5, 2, to the fourth from the bottom (2nd);

Coding practices

public class Test {

	public static void main(String[] args) {
		int n1[] = { 6.5.2.7.1 };
		bubbleSort1(n1);
		System.out.print("Bubble sort method a result:");
		for (int m : n1) {
			System.out.print(m + "");
		}
		System.out.println("");
		int n2[] = { 6.5.2.7.1 };
		bubbleSort1(n2);
		System.out.print("Bubble sorting method two results:");
		for (int m : n2) {
			System.out.print(m + "");
		}
		System.out.println("");
		int n3[] = { 6.5.2.7.1 };
		bubbleSort1(n3);
		System.out.print("Bubble sorting method three results:");
		for (int m : n3) {
			System.out.print(m + ""); }}public static void bubbleSort1(int n[]) {
		for (int i = n.length - 1; i >= 0; i--) {
			for (int j = 0; j < i; j++) {
				if (n[j] > n[j + 1]) {
					int temp = n[j];
					n[j] = n[j + 1];
					n[j + 1] = temp; }}}}public static void bubbleSort2(int n[]) {
		for (int i = n.length - 1; i >= 0; i--) {
			for (int j = 0; j < i; j++) {
				if (n[j] > n[j + 1]) {
					n[j] ^= n[j + 1];
					n[j + 1] ^= n[j];
					n[j] ^= n[j + 1]; }}}}public static void bubbleSort3(int n[]) {
		boolean isSort = false;
		for (int i = n.length - 1; i >= 0 && !isSort; i--) {
			isSort = true;
			for (int j = 0; j < i; j++) {
				if (n[j] > n[j + 1]) {
					n[j] ^= n[j + 1];
					n[j + 1] ^= n[j];
					n[j] ^= n[j + 1];
					isSort = false;
				}
			}
		}
	}
}
Copy the code
  • The results of
Bubble sort method 1 result: 1 2 5 6 7 Bubble sort method 2 result: 1 2 5 6 7 Bubble sort method 3 result: 1 2 5 6 7Copy the code

instructions

Among the above three kinds of bubble sort coding practices, the first one is the most basic writing method of bubble sort; The second uses bit operations to optimize the efficiency of swapping numbers; Thirdly, marker bits are used to determine whether the array is in order so as to avoid further optimization efficiency of traversal of the ordered array.

eggs

Method 2: Swap digits in bubbleSort2

n[j] ^= n[j + 1];
n[j + 1] ^= n[j];
n[j] ^= n[j + 1];
Copy the code

How does exchange work? This is the Easter egg.

conclusion

Bubble sort is one of the simplest sorting algorithms. This paper focuses on the idea and implementation of bubble sort algorithm. Further introduces the bubbling optimization tips, after understanding this article, I believe that in the future to meet the handwritten bubbling sorting scene will be more handy, learn endless. Finally, if you found this article inspiring or helpful, keep an eye out for a wave of 0.0