brief introduction

Sorting is probably the most basic and commonly used of all algorithms. Sorting is a very classic problem. It reorders the items in an array (or a list) in a certain order.

There are many sorting algorithms, each of which has its own advantages and limitations.

Today, let's learn the simplest bubble sorting algorithm.

Bubble sorting principle

The principle of bubble sorting is very simple. Let's imagine the process of bubble floating one by one.

Suppose we have eight numbers 29, 10, 14, 37, 20, 25, 44, 15 to sort.

Let's use an animation to visually observe the whole bubble sorting process:

There are eight rounds of sorting. Each round will make pairwise comparison, and move the larger elements to the right, just like bubbling.

At the end of the round, the largest of the eight elements 44 will move to the far right.

Then repeat the other rounds. Finally, we get a fully sorted array.

You can also look at it this way:

The first round is to move the maximum 44 of the eight elements to the rightmost position. The second round is to move the second largest value 37 exchange of the eight elements to the rightmost position. and so on.

Java implementation of bubble sorting algorithm

Let's first look at the simplest bubbling algorithm:

public class BubbleSort {

    public void doBubbleSort(int[] array){
        log.info("排序前的数组为:{}",array);
        //外层循环,遍历所有轮数
        for(int i=0; i< array.length-1; i++){
            //内层循环，两两比较，选中较大的数字，进行交换
            for(int j=0; j<array.length-1; j++){
                if(array[j]>array[j+1]){
                    //交换两个数字
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            log.info("第{}轮排序后的数组为:{}",i+1,array);
        }
    }

    public static void main(String[] args) {
        int[] array= {29,15};
        BubbleSort bubbleSort=new BubbleSort();
        bubbleSort.doBubbleSort(array);
    }

}

This algorithm is a two-layer traversal, and the outer layer traversal represents the number of rounds. Inner traversal represents each round of sorting.

Let's look at the output:

The first improvement of bubbling algorithm

By analyzing the above traversal process, we can find that after the first sorting, 44 has been placed in the rightmost position and has been sorted.

After the second sorting, 37 has been sorted. After each round, the number of internal cycles that need to be compared can be reduced by one.

This means that in the internal loop, we only need to perform array Length-i-1 comparison is enough.

The modification code is as follows:

public class BubbleSort1 {

    public void doBubbleSort(int[] array){
        log.info("排序前的数组为:{}",遍历所有轮数
        for(int i=0; i< array.length-1; i++){
            //内层循环，两两比较，选中较大的数字，进行交换,最后的i个数字已经排完序了，不需要再进行比较
            for(int j=0; j<array.length-i-1; j++){
                if(array[j]>array[j+1]){
                    //交换两个数字
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
            log.info("第{}轮排序后的数组为:{}",15};
        BubbleSort1 bubbleSort=new BubbleSort1();
        bubbleSort.doBubbleSort(array);
    }

}

Operation results:

We can see that the running results are actually no different, but we have made few comparisons.

The second improvement of bubbling algorithm

From the above results, we can see that the sorting has been completed after the fifth round of sorting. But we still did the 6th and 7th sorting.

Is there any way to judge whether the sorting has been completed?

Let's consider that in the internal loop, we compare two by two and then exchange positions.

If there is no interaction in a certain traversal, it means that the sorting has been completed.

So we can introduce another flag to judge.

public class BubbleSort2 {

    public void doBubbleSort(int[] array){
        log.info("排序前的数组为:{}",遍历所有轮数
        for(int i=0; i< array.length-1; i++){
            //添加一个flag，如果这一轮都没有排序，说明排序已经结束，可以提前退出
            boolean flag=false;
            //内层循环，两两比较，选中较大的数字，进行交换,最后的i个数字已经排完序了，不需要再进行比较
            for(int j=0; j<array.length-i-1; j++){
                if(array[j]>array[j+1]){
                    //交换两个数字
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = true;
                }
            }
            log.info("第{}轮排序后的数组为:{}",array);
            if(!flag)
            {
                log.info("本轮未发生排序变化，排序结束");
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[] array= {29,15};
        BubbleSort2 bubbleSort=new BubbleSort2();
        bubbleSort.doBubbleSort(array);
    }

}

The operation results are as follows:

From the results, we can see that one round of sorting is missing and the speed is improved.

Time complexity of bubble sorting

Although we can do some performance optimization when bubbling, we basically have to do two nested traversals. The number of iterations is approximately = n * n, so the time complexity of the bubble sorting algorithm is O (n) ²)。

Code address of this article:

learn-algorithm