//这是三路快速排序的实现，最重要的是要注意边界值的问题，尤其是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;

    }

}