//三路快速排序O(nlogn)

template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
    if(l>=r) return;
    swap(arr[l],arr[rand()%(r-l)+l])
    T v=arr[l];
    int lt=l; //arr[l+1,lt]<v
    int gt=r+1; //arr[gt,r]>v
    int i=l; //arr[lt+1,i]==v
    while(i<gt)
    {
        if(arr[i]<v)
        {
            swap(arr[i],arr[lt+1]);//小于v和等于v部分的元素交换位置
            lt++;
            i++;
        }
        else if(arr[i]>v)
        {
            swap(arr[i],arr[gt-1]);
            gt--;//i依然是未处理的元素，不动
        }
        else
        {
            i++
        }
    }
    swap(arr[l],arr[lt])
    __quickSort3Ways(arrr,l,lt-1);
    __quickSort3Ways(arr,gt,r);

}

template <typename T>
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}