快速排序

分析：

取一个数P作为基准，然后将小于P的数放在P的左边，大于P的数放在P的右边

JAVA实现：

public class Main {
   
    public static void main(String[] args) {
        int[] arr = new int[100];
        for(int i=0;i<100;i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        sort(arr);
        for(int i=0;i<100;i++){
            System.out.println(arr[i]);
        }
    }
    
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length-1);
    }
    
    public static void sort(int[] arr, int l, int r) {
        if(l > r){
            return;
        }
        int p = arr[l];
        
        int i=l;
        int j=r;
        while(i < j){
            while(i < j && arr[j] >= p) {
                j--;
            }
            while(i < j && arr[i] <= p) {  //必须是小于等于，忽略第一个基准数
                i++;
            }
            if(i<j){
                swap(arr, i,j);
            }
        }
        if(i != l){
            swap(arr, i, l);   //将基准数p和位置i的数进行交换，因为i这个位置的数是小于p的
            sort(arr, l, i-1);
        }
        sort(arr, i+1, r);
    }
    
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
}

下面是数组的交换过程：

原始数组 [4,8,5,0,1,6,3]
交换：3,8
[4, 3, 5, 0, 1, 6, 8]
交换：1,5
[4, 3, 1, 0, 5, 6, 8]
基准交换：4,0
[0, 3, 1, 4, 5, 6, 8]
交换：3,1
[0, 1, 3, 4, 5, 6, 8]