三路快速排序

 

//这是三路快速排序的实现，最重要的是要注意边界值的问题，尤其是lt，gt和i的取值，千万不要弄错了

//下面实现的lt代表的是包括最右边的那个，整个区间是【l,lt】是个闭区间，右边也是个闭区间，所以写代码时要注意，在算法这本书中的实现与我的区间有些不同，请注意。

class Solution {    public static void quickSort(int[] arr,int l,int r)    {        if(l>=r)            return ;        int lt=l,i=l+1,gt=r+1;        int v=arr[l];        while(i<gt)        {            if(arr[i]<v)            {                swap(arr,i,lt+1);                i++;                lt++;            }            else if(arr[i]>v)            {                swap(arr,i,gt-1);                gt--;            }            else            {                    i++;            }        }        swap(arr,l,lt);        quickSort(arr,l,lt-1);        quickSort(arr,gt,r);    }    public static void swap(int[] arr,int x,int y)    {        int temp=arr[x];        arr[x]=arr[y];        arr[y]=temp;    }    public int[] sortArray(int[] nums) {        quickSort(nums,0,nums.length-1);        return nums;    }}

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