快速排序

快排是最基本的排序之一

• 确定分界点（左端点、右端点，中间点？）

• 调整区间

• 调整后的结果就是 左边的都小于 分界点， 右边的都大于分界点 （指针相遇或者穿越过后）
• 递归处理左右两边

如何简单理解算法的思想：
可以这样想：两个指针从左端和右端往中间走，当重合穿过时，指针左边都小于选取的门限值，右边都大于门限值，再递归左右两边的数组

import java.util.*;
import java.io.*;

public class Main{


    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++){
            arr[i] = sc.nextInt();
        }

        quick_sort(arr,0,n-1);
        for(int i = 0; i < n; i++){
            System.out.print(arr[i]+" ");
        }
    }

    //核心模板代码
    private static void quick_sort(int[] arr, int l, int r){
        if(l >= r) return;

        int p = arr[l]; //我们取左端点
        int i = l-1;
        int j = r+1;

        while(i < j){

            do{
                i++;
            }while(arr[i]<p);

            do{
                j--;
            }while(arr[j]>p);
            if(i < j){
                        //交换
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }



        //递归
        quick_sort(arr, l, j);
        quick_sort(arr, j+1, r);
    }


}