Bubble sorting

The size of two adjacent elements is compared. If the current element is larger than the element on the right, it will be exchanged, otherwise it will not be exchanged;
A total of N-1 rounds are arranged, and the largest element in the disordered area is selected in each round;
A round needs to be compared N-1 times, and there are N-1 rounds in total, so the time complexity is N*N;

The original version (also the first time to learn data structure and try to memorize the algorithm!)

    public static void sort(int array[]){
        for(int i = 0; i < array.length - 1; i++)
        {
            for(int j = 0; j < array.length - i - 1; j++)
            {
                int tmp = 0;
                if(array[j] > array[j+1])
                {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args){
        int[] array = new int[]{5,8,6,3,9,2,1,7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

First optimization (solve the problem that the disordered area on the left has been ordered)

In the following figure, the sixth round of sorting has been ordered. In fact, the last round of sorting can be ended in advance.

    public static void sort(int array[]) {
        for (int i = 0; i < array.length - 1; i++) {
            //The initial value of each round is true
            boolean isSorted = true;
            for (int j = 0; j < array.length - i - 1; j++) {
                int tmp = 0;
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    //Because there are elements to exchange, it is not ordered, and the tag becomes false
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

Second optimization (solve the problem that the disordered area on the right side has been ordered)

At this time, the first optimization method can be combined with the flag bit to solve the problem of orderly and redundant comparison cycle in the left and right disordered area

    public static void sort(int array[])
    {
        int tmp  = 0;
        //Record the location of the last exchange
        int lastExchangeIndex = 0;
        //The boundary of the unordered sequence, each comparison only needs to be compared so far
        int sortBorder = array.length - 1;
        for(int i = 0; i < array.length; i++)
        {
            //The initial value of each round is true
            boolean isSorted = true;

            for(int j = 0; j < sortBorder; j++)
            {
                if(array[j] > array[j+1])
                {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //There is element exchange, so it is not ordered, and the tag becomes false
                    isSorted = false;
                    //Update the boundary of the unordered sequence to the position of the last exchange element
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if(isSorted){
                break;
            }
        }
    }

    public static void main(String[] args){
        int[] array = new int[]{3,4,2,1,5,6,7,8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

The third optimization [cocktail sorting] (in the case of most elements in order, solve the redundant comparison cycle occasionally caused by an inappropriate position of an element)

As shown in the figure below, 1 is the culprit

After optimization using cocktail sorting:

This is the first round (Lai + Hui). This round trip is equivalent to two rounds of the original bubble sorting algorithm, so the outermost loop only needs half of the total array length;
The indexes in the two cycles of odd and even algorithms are always controlled from I to array Between length-i-1, with the increase of I, the disordered area slowly disappears in the middle. Therefore, with the increase of the number of iterations, you only need to sort the disordered area in the middle.

    public static void sort(int array[])
    {
        int tmp  = 0;
        for(int i=0; i<array.length/2; i++)
        {
            //The initial value of each round is true
            boolean isSorted = true;
            //Odd wheel, compare and exchange from left to right
            for(int j=i; j<array.length-i-1; j++)
            {
                if(array[j] > array[j+1])
                {
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    //There is element exchange, so it is not ordered, and the tag becomes false
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }

            //Before even rounds, re mark as true
            isSorted = true;
            //Even wheel, compare and exchange from right to left
            for(int j=array.length-i-1; j>i; j--)
            {
                if(array[j] < array[j-1])
                {
                    tmp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = tmp;
                    //There is element exchange, so it is not ordered, and the tag becomes false
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }
        }
    }

    public static void main(String[] args){
        int[] array = new int[]{2,3,4,5,6,7,8,1};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

It can be used in combination with the optimization method of flag bit (the first method) and the last index method of recording disordered areas (the second method).
*Examples are from comic algorithm