Bubble sort and quick sort

1、 Bubble sort

1.1、 Basic introduction

• Bubble sort (Bubble Sorting） The basic idea of ： By treating the sort sequence from front to back （ Start with elements with smaller subscripts ,, Compare the values of adjacent elements in turn , If reverse order is found, exchange , Gradually move the higher value elements from the front to the back , It's like a bubble under the water coming up .

• Because in the process of sorting , Each element keeps getting closer to its place , If there is no exchange after comparison , It means that the sequence is orderly , Therefore, set a flag in the sorting process flag Determine whether elements have been exchanged . So as to reduce unnecessary comparison .

1.2、 Code implementation

// Ascending sort 
// Time complexity of bubble sort  O(n²)
public class BubbleSort {
    
   
    public static void main(String[] args) {
    
        int[] arr = {
    9,4,2,6,3,7,4,1};
		bubbleSort(arr);
        System.out.println(" After ordering ");
        System.out.println(Arrays.toString(arr)); 
    }

    public static void bubbleSort(int[] arr){
    
        int temp = 0; // Temporary variable 
        boolean flag = false; // Identifying variables , Indicates whether an exchange has occurred 
        for (int j = 0; j < arr.length - 1; j++) {
    
            for (int i = 0; i < arr.length - 1 - j; i++) {
    
                // If the front number is larger than the back number , Just exchange 
                if(arr[i] > arr[i+1]){
    
                    flag = true;
                    temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                }
            }   

            if(!flag){
     // In a sequence , No exchange has ever happened 
                break;
            }else{
    
                flag = false; // Reset flag, Make the next judgment 
            }
        }
    }
}

2、 Quick sort

2.1、 Introduce

• Quick sort （Quicksort） It's an improvement on bubble sort .

• The basic idea yes ： Divide the data to be sorted into two independent parts by one sorting , All the data in one part is smaller than all the data in the other part , Then according to this method, the two parts of data are sorted quickly , The whole sorting process can recursive （ Open stack , Need space ） Conduct , So that the whole data becomes an ordered sequence

2.2、 Code implementation

// Quick sort 
public class QuickSort {
    
    public static void main(String[] args) {
    
        int[] arr = {
    15, 0, 10, 5, 25};
        quickSort(arr,0, arr.length-1);
        System.out.println("arr="+ Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
    
        int l = left; // Left subscript 
        int r = right; // Right subscript 
        //pivot  Central axis 
        int pivot = arr[(left + right) / 2];
        int temp = 0; // Temporary variable 
        //while The purpose of the cycle is to make a comparison pivot Small values are placed on the left ; Than pivot Big value to the right 
        while (l < r) {
    
            // stay pivot I 've been looking for it on the left side of , Find greater than or equal to pivot Value , Just quit 
            while (arr[l] < pivot) {
    
                l++;
            }
            // stay pivot I 've been looking for , Find less than or equal to pivot Value , Just quit 
            while (arr[r] > pivot) {
    
                r--;
            }
            // If l>=r establish , explain pivot The left and right values of , It's all less than or equal to... On the left pivot Value , And on the right are all greater than or equal to pivot Value 
            if (l >= r) {
    
                break;
            }

            // In exchange for 
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // If after the exchange , Found this arr[l] == pivot Value ,r-- , Move forward 
            if (arr[l] == pivot) {
    
                r--;
            }

            // If after the exchange , Found this arr[r] == pivot Value ,l++ , Move backward 
            if (arr[r] == pivot) {
    
                l++;
            }
        }

        // If  l==r , must l++,r--, Otherwise, there will be a stack overflow 
        if(l==r){
    
            l++;
            r--;
        }
        // Left recursion 
        if(left <r){
    
            quickSort(arr,left,r);
        }
        // Right recursion 
        if(right >l){
    
            quickSort(arr,l,right);
        }
    }
}