快速排序

 

 

 

 

 

 

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;    }}

转载于:https://www.cnblogs.com/cold-windy/p/11187044.html