昨天拼多多笔试，一道算法题是快排，没写出来，整了个冒泡排序上去，尴尬。温故而知新，今天复习一下。

题目：给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

class Solution {
    //快排
    public int[] sortArray(int[] a) {
        quick(a,0,a.length-1);
        return a;
    }
    void quick(int[] a,int left,int right){
        if(left>=right) return;
        //第一次快排得到基准位置
        int p = partition(a,left,right);
        //递归基准位置左面的子数组和右面的子数组，其实就是一直二分排序，直到子数组为空
        quick(a,left,p-1);
        quick(a,p+1,right);
    }
    int partition(int[] a,int left,int right){
        //随机选中一个索引下标为基准
        int idx = ThreadLocalRandom.current().nextInt(right-left+1) + left;
        //把基准数字移到最左端
        swap(a,left,idx);
        //基准值
        int pv = a[left];
        //左指针
        int i = left +1;
        //右指针
        int j = right;
        //循环遍历左右指针
        while(i<=j){
            //左指针停在比基准大的数上面
            while(i<=j && a[i] < pv){
                i++;
            }
            //右指针停在比基准值小的数上面
            while(i<=j&& a[j] > pv){
                j--;
            }
            //如果左指针比又指针小，交换左右指针,然后左右指针都移动一步
            if(i<=j){
                swap(a,i,j);
                i++;
                j--;
            }
        }
        //遍历结束后，将基准值移到右指针的位置，这样就能保证基准值前面的数小于基准值，后面的数大于基准值
        swap(a,left,j);
        //返回基准值的位置，索引
        return j;
    }
    void swap(int[] a,int left,int right){
        int tmp = a[left];
        a[left] = a[right];
        a[right] = tmp;
    }}
   

其实就是双指针一直移动，递归二分。