Introduction to the

Bubble sort is a very mainstream sort algorithm, Bubble sort, which is a basic exchange sort.

Principle: Compare two adjacent elements, swap the element with the largest value to the right end.

Idea: Compare neighboring elements in pairs, and when one element is larger than the neighboring element on the right, swap their positions. When an element is less than or equal to its neighbor on the right, the position does not change.

For example: to sort an array: int[] array={5,8,6,3,9,2,1,7};

First order:

First sort: 5 and 8 compare, 5 is less than 8, same position: 5,8,6,3,9,2,1,7

Second order: compare 8 with 6,8 is greater than 6, switch positions: 5,6,8,3,9,2,1,7

Third order: compare 8 and 3,8 is greater than 3, switch positions: 5,6,3,8,9,2,1,7

Fourth order: compare 8 and 9, 8 is less than 9, same position: 5,6,3,8,9,2,1,7

5,6,3,8,2,9,1,7

Compare 9 and 1,9 is less than 1, switch places: 5,6,3,8,2,1,9,7

Compare 9 with 7,9 is less than 7, switch places: 5,6,3,8,2,1,7,9

Second order:

First sort: 5 and 6 compare, 5 is less than 6, same position: 5,6,3,8,2,1,7,9

Second order: compare 6 with 3,6 is greater than 3, switch positions: 5,3,6,8,2,1,7,9

Third order: 6 and 8, 6 is less than 8, same position: 5,6,3,8,2,1,7,9

Fourth order: compare 8 and 2,8 is greater than 2, switch positions: 5,6,3,2,8,1,7,9

5,6,3,2,1,8,7,9

Compare 8 and 7,8 is greater than 7, switch places: 5,6,3,2,1,7,8,9

Number 7: compare 8 to 9,8 is less than 9, same position: 5,6,3,2,1,7,8,9

Third order:

First sort: 5 and 6 compare, 5 is less than 6, same position: 5,6,3,2,1,7,8,9

Second order: compare 6 with 3,6 is greater than 3, switch positions: 5,3,6,2,1,7,8,9

Third sort: compare 6 with 2,6 is greater than 2, switch places: 5,3,2,6,1,7,8,9

Fourth sort: compare 6 with 1,6 is greater than 1, switch positions: 5,3,2,1,6,7,8,9

5,3,2,1,6,7,8,9

5,3,2,1,6,7,8,9

Number 7: compare 8 to 9,8 is less than 9, same position: 5,3,2,1,6,7,8,9

Fourth order:

First sort: 5 and 3 compare,5 is greater than 3, switch positions: 3,5,2,1,6,7,8,9

Second order: compare 5 with 2,5 is greater than 2, switch positions: 3,2,5,1,6,7,8,9

Third sort: compare 5 with 1,5 is greater than 1, switch places: 3,2,1,5,6,7,8,9

3,2,1,5,6,7,8,9

3,2,1,5,6,7,8,9

3,2,1,5,6,7,8,9

Number 7: compare 8 to 9,8 is less than 9, same position: 3,2,1,5,6,7,8,9

Fifth order:

First sort: compare 3 with 2,3 is greater than 2, switch positions: 2,3,1,5,6,7,8,9

2,1,3,5,6,7,8,9

2,1,3,5,6,7,8,9

Fourth order: 5 and 6, 5 is less than 6, same position: 2,1,3,5,6,7,8,9

Number 5:2,1,3,5,6,7,8,9

2,1,3,5,6,7,8,9

Number 7: compare 8 to 9,8 is less than 9, same position: 2,1,3,5,6,7,8,9

Sixth order:

First sort: compare 2 with 1,2 is greater than 1, switch places: 1,2,3,5,6,7,8,9

1,2,3,5,6,7,8,9

1,2,3,5,6,7,8,9

Fourth order: 5 and 6, 5 is less than 6, same position: 1,2,3,5,6,7,8,9

Number 5:1,2,3,5,6,7,8,9

1,2,3,5,6,7,8,9

Number 7:8 is less than 9, 1,2,3,5,6,7,8,9

Seventh order:

1,2,3,5,6,7,8,9

1,2,3,5,6,7,8,9

1,2,3,5,6,7,8,9

Fourth order: 5 and 6, 5 is less than 6, same position: 1,2,3,5,6,7,8,9

Number 5:1,2,3,5,6,7,8,9

1,2,3,5,6,7,8,9

Number 7:8 is less than 9, 1,2,3,5,6,7,8,9

Sorting results: 1,2,3,5,6,7,8,9

/** * Bubble sort definition: we want to compare two adjacent elements in pairs, when one element is greater than the right of the adjacent element, * swap their position: when one element is less than or equal to the right of the adjacent element, the position is the same */
public class demo1 {

    public static void main(String[] args) {
        int array[] = {5.8.6.3.9.2.1.7};

        sortBig(array);
        System.out.println("From largest to smallest:"+ Arrays.toString(array));

        sortSmall(array);
        System.out.println("From small to large:"+ Arrays.toString(array));
    }

    /** * sort from largest to smallest *@paramArray an array of * /
    private static void sortBig(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[i] > array[j]){ temp = array[i]; array[i] = array[j]; array[j] = temp; }}}}/** * sort from smallest to largest *@paramArray an array of * /
    private static void sortSmall(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[j] > array[j +1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

}

Copy the code

The code is sorted using a double loop: the outer loop controls all the turns, and the inner loop performs the bubbling of each turn, comparing elements first and then exchanging them.

Execution Result:

From large to small: [9, 8, 7, 6, 5, 3, 2, 1]

From small to large: [1, 2, 3, 5, 6, 7, 8, 9]

To optimize the

Let’s review the sorting details just described, {5,8,6,3,9,2,1,7} when the sorting algorithm is executed on round 6 and round 7 respectively

It’s clear that by the sixth round, the sequence is already in order. But the sorting algorithm still ran its seventh round

In this case, if you can determine that the sequence is in order and mark it, then the remaining rounds of sorting don’t have to be performed and you can end the work early.

Bubble sort code optimization:

/** * Bubble sort optimization * definition: we want to compare two adjacent elements in pairs, when one element is greater than the right of the adjacent element, * swap their position: when one element is less than or equal to the right of the adjacent element, the position is the same */
public class demo1 {

    public static void main(String[] args) {
        int array[] = {5.8.6.3.9.2.1.7};

        sortBig(array);
        System.out.println("From largest to smallest:"+ Arrays.toString(array));

        sortSmall(array);
        System.out.println("From small to large:"+ Arrays.toString(array));
    }

    /** * sort from largest to smallest *@paramArray an array of * /
    private static void sortBig(int[] array) {
        for (int i = 0; i < array.length; i++) {
            / / tag
            boolean flag = true;
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[i] > array[j]){
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    // There are elements swapping, so it is not ordered
                    flag = false; }}if(flag){
                break; }}}/** * sort from smallest to largest *@paramArray an array of * /
    private static void sortSmall(int[] array) {
        for (int i = 0; i < array.length; i++) {
            / / tag
            boolean flag = true;
            for (int j = 0; j < array.length - 1 ; j++) {
                int temp = 0;
                if(array[j] > array[j +1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    // There are elements swapping, so it is not ordered
                    flag = false; }}if(flag){
                break; }}}}Copy the code

Use the Boolean variable flag as the flag. If there is a swap, the list is unordered. If there is no swap, the list is ordered, jumping out of the big loop and further improving performance.

---

“When there is a high wind, life does not give up”