(if you are a freshman, you should not panic and study patiently. In fact, it's not very difficult. What I regret most is that I felt it was very difficult when I was a freshman and didn't want to see it, but you should know these things sooner or later. Don't stick the code in the experiment class, and you must fight with your own hands

The above is the advice of the elder sister:))

 

Quick sort problem:

Compare the last number in the array, set it to x, and arrange the whole array as [< x part, = x part, > x part]

Then recursively process the array on the left and the array on the right

As in the first step, the last number of the left array is set to X (this x is the number = x position-1, which is the last number of the left array). Follow the first step

The right array has the same operation as the left array above

Implementation code:

package basic_class_01;

public class quickSort {

    public static void quickSort(int arr[]){
        if(arr==null||arr.length<=2){//If the array is empty, or the number in the array is less than two, it ends directly
            return;
        }
        quickSort(arr,0,arr.length-1);
    }
    public static void quickSort(int arr[],int l,int r){
        if(l<r){
            int[] p=partition(arr,l,r);//We get the left position and the right position equal to the region
            quickSort(arr,l,p[0]-1);//Operation on left array
            quickSort(arr,p[1]+1,r);//Operate on the right array
        }
    }
    public static int[] partition(int arr[],int l,int r){
        int less=l-1;//Starting position-1
        int more=r;//Rightmost position
        while(l<more){//Jump out of loop when pointing to > x
            if(arr[l]<arr[r]){//If the pointing position is less than x, the number of pointing positions and the next number less than the region are swapped
                swap(arr,++less,l++);
            }
            else if(arr[l]>arr[r]){//If the pointing position is greater than x, exchange the number of pointing positions with the previous position greater than the region
                swap(arr,--more,l);
            }
            else{
                l++;//If the number of points is equal to x, then there is no need to exchange, pointing to the next number
            }
        }
        swap(arr,more,r);//Let x and the first number greater than the region swap
        return new int[] {less+1,more};//There are two numbers in the return array. The first number is equal to the position of the first number in the region, and the second number is equal to the position of the last number in the region
    }
    public static void swap(int a[],int l,int r){
        int tmp=a[l];
        a[l]=a[r];
        a[r]=tmp;

    }
    public static void main(String[] args) {
        int arr[]={0,6,7,8,9,1,2,3,4,5};
        quickSort(arr,0,arr.length-1);//The range passed into the entire array
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);//Output the last ordered array
        }
    }
}