class Solution {

    //quickSort函数

    public static void quickSort(int[] arr,int l,int r){

        if(l>=r)

        {

            return ;

        }

        int p=partition(arr, l, r);         //找到分界点的下标位置

        quickSort(arr,l,p-1);

        quickSort(arr,p+1,r);

    }

    //partition函数，找到第一个元素在数组中的位置，将数组分成两块

    public static int partition(int[] arr,int l,int r)

    {

        //随机生成一个下标，用来作为这个初始的l，将它与l下标的元素交换一下，再将l位置作为我们的v

        //下面的代码注释掉是为了提高在leetcode上的运行时间，最好加上这几行代码，具体作用之前已经讲过。

//         Random m=new Random();

//         int k= m.nextInt(r-l)+l;

//         int tp=arr[k];

//         arr[k]=arr[l];

//         arr[l]=tp;

        

        

        //将随机化过后的第一个l位置的元素作为我们选择好的v

        int v=arr[l];

       //对于区间[l,i)来说，都是不大于v的，i是当前要判断的那个位置的下标  

        //而对于区间(j,r]来说，都是不小于v的，j是我们当前要判断的这个位置的下标

        int i=l+1;      //要判断的第一个i的值

        int j=r;        //要判断的第一个j的值

        while(true)

        {

            while(i<=r&&arr[i]<v) i++;          //对于i值满足arr【i】小于v，就一直往前走，直到遇见一个不满足条件的，前提要满足边界条件 i<=r;

            while(j>=l+1&&arr[j]>v) j--;        //----------------------------------------------------------------------------一样参上

            if(i>j)                            //上面两个式子都找到了满足条件的，需要交换了，但是前提需要判断一下i和j的顺序，如果此时i和j已经相遇了，说明数组已经是                                                                                                                                   有序了，可以直接break出去了

            {

                break;

            }

            //交换一下元素位置

            int temp=arr[i];

            arr[i]=arr[j];

            arr[j]=temp;

            //i和j继续

            i++;

            j--;

        }

        int swap=arr[j];

        arr[j]=v;

        arr[l]=swap;

        return j;

    }

    public int[] sortArray(int[] nums) {

        quickSort(nums,0,nums.length-1);

        return nums;

    }

}