Bubble sorting

1. What is Bubble sorting？

Bubble Sort is the most basic exchange sort. The reason why it is called bubble sorting is that each element can be sorted bit by bit according to its own size like a small bubble array Move to one side of the.

Principle of bubble sorting:

Only one number can be determined to be returned in each trip. That is, the first trip can only determine to return the number on the last digit, the second trip can only return the number on the penultimate digit, and so on. If there are n numbers to sort, just return the N-1 numbers, that is, n-1 operations.

For "each trip", you need to compare the two adjacent numbers from the first place, put the larger number behind, move back one bit after the comparison, continue to compare the size relationship of the next two adjacent numbers, and repeat this step until the last number has not returned.

2. How is bubble sorting sorted?

Let's take a look at how bubble sorting moves through a dynamic diagram

Assuming that the sequence to be sorted is (5,1,4,2,8), if bubble sorting is used to sort them in ascending order (from small to large), the whole sorting process is as follows:

1) In the first round of sorting, at this time, the elements in the whole sequence are located in the sequence to be sorted. Scan each pair of adjacent elements in turn, and exchange positions for element pairs with incorrect order. The whole process is shown in Figure 1.

As can be seen from Figure 1, after the first round of bubble sorting, the maximum number of 8 is found from the sequence to be sorted, and it is placed at the end of the sequence to be sorted and incorporated into the sorted sequence.

2) In the second round of sorting, at this time, the sequence to be sorted only contains the first four elements. Scan each pair of adjacent elements in turn, and exchange positions for elements with incorrect order. The whole process is shown in Figure 2.

It can be seen that after the second round of bubble sorting, the maximum number of 5 is found from the sequence to be sorted, which is placed at the end of the sequence to be sorted and incorporated into the sorted sequence.

3) The third round of sorting. At this time, the sequence to be sorted contains the first three elements. Scan each pair of adjacent elements in turn, and exchange positions for elements with incorrect order. The whole process is shown in Figure 3.

After this round of bubble sorting, the maximum number of 4 is found from the sequence to be sorted, and it is placed at the end of the sequence to be sorted and incorporated into the sorted sequence.

4) The fourth round of sorting. At this time, the sequence to be sorted contains the first two elements. The whole process of bubble sorting is shown in Figure 4.

After this round of bubble sorting, the maximum number 2 is found out from the sequence to be sorted, put it at the end of the sequence to be sorted and incorporated into the sorted sequence.

5) When the fifth round of bubble sorting is carried out, since there is only one element left in the sequence to be sorted, no matter the comparison of adjacent elements is carried out, it is directly incorporated into the sorted sequence, and the sequence at this time is recognized as the sorted sequence (as shown in Figure 5).

3. Bubble sorting characteristics

💫 N numbers are sorted in n-1 rounds

💫 Compare in pairs to put the maximum value in the last position

The bubbling code is still quite simple. It is well known in the Jianghu that the two-layer cycle, the number of bubbling rounds in the outer layer and the inner layer are compared in turn.

• 1. Compare two adjacent elements in the array. If the first number is larger than the second, we will exchange their positions
• 2. Each comparison will produce a maximum or minimum number;
• 3. In the next round, you can sort less once
• 4. One cycle until the end!

4. Bubble sort code

public class ArrayDemo07 {
    public static void main(String[] args) {
        int[] a={231,112,12321,321,3232};
        int[] sort = sort(a);//After calling the sorting method written by ourselves, return a sorted array
        System.out.println(Arrays.toString(sort));

    }
    //Bubble sorting
    //1. Compare two adjacent elements in the array. If the first number is larger than the second number, we will exchange their positions
    //2. Each comparison will produce a maximum or minimum number;
    //3. In the next round, you can sort less once
    //4. One cycle until the end!

    public static int[] sort(int[] array){
        //Temporary variable
        int temp=0;
        //Outer circulation, judge how many times we have to go;
        for (int i = 0; i < array.length-1; i++) {
            //Inner loop: compare and judge two numbers. If the first number is larger than the second number, exchange the position 
            for (int j = 0; j < array.length-1-i; j++) {
                //By changing the exchange order here, large exchange and small exchange change the sorting method
                if (array[j+1]<array[j]){
                    temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
                
            }

        }
        return array;
    }
}

💥 Thinking: how to optimize?

💥 The flag flag flag bit is used to reduce meaningless comparison

public class ArrayDemo07 {
    public static void main(String[] args) {
        int[] a={231,112,12321,321,3232};
        int[] sort = sort(a);//After calling the sorting method written by ourselves, return a sorted array
        System.out.println(Arrays.toString(sort));

    }
    //Bubble sorting
    //1. Compare two adjacent elements in the array. If the first number is larger than the second number, we will exchange their positions
    //2. Each comparison will produce a maximum or minimum number;
    //3. In the next round, you can sort less once
    //4. One cycle until the end!

    public static int[] sort(int[] array){
        //Temporary variable
        int temp=0;
        //Outer circulation, judge how many times we have to go;
        for (int i = 0; i < array.length-1; i++) {
            boolean flag=false;//The flag flag flag bit is used to reduce meaningless comparison
            //Inner loop: compare and judge two numbers. If the first number is larger than the second number, exchange the position 
            for (int j = 0; j < array.length-1-i; j++) {
                if (array[j+1]<array[j]) {//By changing the exchange order here, large exchange and small exchange change the sorting method
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;
                }
            }
            if (flag==false){
                break;
            }
        }
        return array;
    }
}