Brief introduction of bubble sort and quick sort

1、 Bubble sort

Compare two at a time adjacent The elements of , And in accordance with the Ascending or descending Replace the position according to the rules of , You need to use double-layer loop traversal , Each cycle will only sort one value , A total of n-1 Time ;

stability ： Stable , Two elements with the same value will not exchange positions ;

Time complexity ：O(n2);

Spatial complexity ：1

usage ： Suitable for small amounts of data ;

Code implementation ：

    public static void main(String[] args) {
    
        //  Bubble sort 
        int[] a = {
    2, 5, 9, 7, 8, 1, 4};
        for (int i = 0; i < a.length - 1; i++) {
    
            for (int j = 0; j < a.length - 1 - i; j++) {
    
                if (a[j] > a[j + 1]) {
    
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    } 

2、 Quick sort

First step ： Find a benchmark , In a dichotomy , Find a... From the array base Elements ( Generally, the first element is the cardinality ) Divide a string of data into two strings ;

The second step ： Partition , Rearrange the array , Will be less than base Put the element on the left , Greater than base Put the element on the right , Put the same value anywhere , bring base Become an intermediate element ;

The third step ： recursive , Sort the elements of the two groups separately ;

stability ： unstable , Two elements with the same value may exchange positions ;

Time complexity ：O(nlogn), If base If it is just the maximum or minimum value, it is O(n2);

Spatial complexity ：O(nlogn), If base If it is just the maximum or minimum value, it is O(n);

usage ： Suitable for small amounts of data ;

Code implementation ：

public static void main(String[] args) {
    
    int[] b = {
    4, 5, 9, 7, 8, 1, 4, 3, 7, 9, 10};
    quickSort(b, 0, b.length - 1);
} 


private static void quickSort(int[] b, int left, int right) {
    
        if (left > right) {
    
            return;
        }
        int i = left;
        int j = right;
        //temp It's the reference level 
        int temp = b[left];

        while (i < j) {
    
            // First look at the right side , To the left 
            while (temp <= b[j] && i < j) {
    
                j--;
            }
            // Look at the left side , Increase right in turn 
            while (temp >= b[i] && i < j) {
    
                i++;
            }
            // If the conditions are met, exchange 
            if (i < j) {
    
                int t = b[j];
                b[j] = b[i];
                b[i] = t;
            }

        }
        //  Compare cardinality with i=j Location data exchange , Generate new cardinality at one time , And the data at both ends will be processed recursively 
        b[left] = b[i];
        b[i] = temp;
        // Recursively call the left half array 
        quickSort(b, left, j - 1);
        // Recursively call right half array 
        quickSort(b, j + 1, right);
}