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

//这对于防止快速排序算法退化为O（N2）级别的算法是有效的，但是在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];

        int j=l;

        for(int i=l+1;i<=r;i++)

        {

            if(arr[i]<v)

            {

                int temp=arr[j+1];

                arr[j+1]=arr[i];

                arr[i]=temp;

                j++;

            }

        }

        int temp=arr[j];

        arr[j]=v;

        arr[l]=temp;

        return j;

    }

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

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

        return nums;

    }

}