1. Bubble sort

1.1 Bubble sorting for first recognition

First sort:

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] array = {1.5.3.4.2.0};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

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

The console output is as follows: [1, 3, 4, 2, 0, 5].

  public class BubbleSortTest {
    public static void main(String[] args) {
        int[] array = {3.4.2.1.5.6.7.8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int array[]) {
        // The total number of times to sort is array.length-1
        for (int j = 0; j < array.length - 1; j++) {
            System.out.format("%d times: \n", j+1);
            for (int i = 0; i < array.length-1-j; i++) {
                int temp = 0;
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                }
                System.out.format("Exchange for the %d pass:", j+1,i+1);
            }
            System.out.format("%d final result:", j+1); }}}Copy the code

Console output:

[1, 5, 3, 4, 2, 0] [1, 3, 5, 4, 2, 0] [1, 3, 4, 5, 2, 0] [1, 3, 4, 2, 5, 0] [1, 3, 4, 2, 0, 5] times 1:1 times the first exchange: 2nd swap of 1st pass: 3rd swap of 1st pass: 4th swap of 1st pass: 5th swap of 1st pass: 6th swap of 1st pass: 7th swap of 1st pass: 1st Pass Final result: 2nd Pass: 1st swap of 2nd pass: 1st pass: 2 times the second exchange: 2 times 3 times exchange: 2 times 4 times exchange: the exchange of the 5th 2 times, 2 times the sixth exchange: 2 times the end result: 3 times: 3 times of the first exchange: 3 times of the second exchange: 3rd swap of the 3rd: 4th swap of the 3rd: 5th swap of the 3rd: 3rd Final result: 4th Swap of the 4th: 1st swap of the 4th: 2nd swap of the 4th: 4th swap of the 4th: 4th Final result: 5 times, 5 times the first exchange: this is the second time 5 times exchange: exchange over 3 times 5:5 times the end result: 6 times: 6 times of the first exchange: 6 times of the second exchange: 6 times the end result: 7 times: 7 times the first exchange: 7th final result: [1, 2, 3, 4, 5, 6, 7, 8]Copy the code

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] array = {3.4.2.1.5.6.7.8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void sort(int array[]) {
        // The total number of times to sort is array.length-1
        for (int j = 0; j < array.length - 1; j++) {
            System.out.format("%d times: \n", j+1);
            boolean flag=true;
            for (int i = 0; i < array.length-1-j; i++) {
                int temp = 0;
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    flag=false;
                }
                System.out.format("Exchange for the %d pass:", j+1,i+1);
            }
            if (flag){
                break;
            }
            System.out.format("%d final result:", j+1); }}}Copy the code

1.2 Sorting Optimization

We can see that on the fourth sort, the sorting is complete, so we can optimize further:

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] array = {3.4.2.1.5.6.7.8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void sort(int array[]) {
        // The total number of times to sort is array.length-1
        for (int j = 0; j < array.length - 1; j++) {
            boolean flag = true;
            for (int i = 0; i < sortBorder; i++) {
                int temp = 0;
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    flag = false; }}if (flag) {
                return; }}}}Copy the code

1st pass: 1st pass: 1st pass: 2nd pass: 1st pass: 3rd pass: 1st pass: 4th pass: 1st pass: 5th pass: 1st pass: 6th pass: 1st pass: 7th pass: 1st pass final result: 2nd pass: 2nd pass: 1st pass: 5th pass: 6th pass: 1st pass: 7th pass: 1st pass: 1st pass: 7th pass: 1st pass The first switch of the second pass: the second switch of the second pass: the third switch of the second pass: the fourth switch of the second pass: the fifth switch of the second pass: the sixth switch of the second pass: the second final result: the third pass: the first switch of the third pass: the second pass: the sixth switch of the second pass: the second final result: the third pass: the first switch of the third pass: 3 times of the second exchange: 3 times of the third exchange: 3 times 4 times exchange: the exchange of the fifth 3 times, 3 times the end result: 4 times: first exchange of 4:4 times the second exchange: the exchange of 3 times 4 times: The fourth exchange of the fourth pass: [1, 2, 3, 4, 5, 6, 7, 8]Copy the code

1.3 Further Optimization

The array {3,4,2,1,5,6,7,8} has been sorted from 5, and has been compared so many times. This is another point we can optimize.

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

    public static void sort(int array[]) {
        // The total number of times to sort is array.length-1
        int lastExchangeIndex = 0;
        int sortBorder = array.length - 1;
        for (int j = 0; j < array.length - 1; j++) {
            System.out.format("%d times: \n", j + 1);
            boolean flag = true;
            for (int i = 0; i < sortBorder; i++) {
                int temp = 0;
                if (array[i] > array[i + 1]) {
                    temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    flag = false;
                    lastExchangeIndex = i;
                }
                System.out.format("Exchange for the %d pass:", j + 1, i + 1);
            }
            sortBorder = lastExchangeIndex;
            if (flag) {
                break;
            }
            System.out.format("%d final result:", j + 1); }}}Copy the code

1st pass: 1st pass: 1st pass: 2nd pass: 1st pass: 3rd pass: 1st pass: 4th pass: 1st pass: 5th pass: 1st pass: 6th pass: 1st pass: 7th pass: 1st pass final result: 2nd pass: 2nd pass: 1st pass: 5th pass: 6th pass: 1st pass: 7th pass: 1st pass: 1st pass: 7th pass: 1st pass Final result: final result: final result: final result: final result: final result: final result: final result: final result: final result: final result: fourth result: [1, 2, 3, 4, 5, 6, 7, 8]Copy the code

As you can see from the results, the number of comparisons is much less.

2. Quicksort

2.1 What is Quicksort?

Like bubble sort, quicksort is a swap sort, where elements are compared and swapped.

The difference isBubble sort can bubble only one element to the other end of the sequence in each round, whereas quicksort splits the sequence into two parts by picking a base element and moving other elements larger than it to one side and smaller elements to the other side of the sequence.

This idea is called divide-and-conquer.