快速排序

两种快速排序

https://www.bilibili.com/video/av62621532/?redirectFrom=h5

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int a[] = {1,5,7,4,23,456,100,3,2,6,10,45,68,0};
        quick_sort(a,0,a.length-1);
        for(int i = 0 ; i < a.length ; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static void quick_sort(int a[] , int L ,int R) {
        if(L>=R)return ;
        int l = L;
        int r = R;
        int pivot = a[l] ;  //没必要l--;
        while(l<r) {        //if不要漏了
            while(l<r&&pivot<=a[r]) 
                r--;
            if(l<r)             
                a[l++] = a[r];
            while(l<r&&pivot>=a[l]) 
                l++;
            if(l<r)               
                a[r--] = a[l];
            if(l>=r)a[r] = pivot;  //记得归还
        }
        quick_sort(a,L,l-1);
        quick_sort(a,l+1,R);
        a[l] = pivot;
    }
}

https://www.bilibili.com/video/av47837026

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int a[] = {71,35,72,243,243,243,100,33,62,56,150,545,658,40};
        quick_sort(a,0,a.length-1);
        for(int i = 0 ; i < a.length ; i++) {
            System.out.print(a[i]+" ");
        }    
    }
    public static void quick_sort(int a[] , int L ,int R) {
        if(L>=R)return ;
        int l = L;
        int r = R-1;
        int pivot = a[R] ;
        int i = l-1 ;           //注意点
        int j = l ;
        while(j<=r) {
            if(a[j]<pivot) {
                i++;            //注意点
                int b = a[i];a[i]=a[j];a[j]=b;
            }
            j++;
        }
        int c = a[R];a[R]=a[i+1];a[i+1]=c; //注意点
        quick_sort(a,L,i);
        quick_sort(a,i+2,R);  //注意点
    }
}