function quickSort(arr, L, R){
    if(L < R){
        let rand = getRandomInt(L, R);
        swap(arr, rand, R);//随机快排
        let p = partition(arr, L, R);
        quickSort(arr, L, p[0] - 1);
        quickSort(arr, p[1] + 1, R);
    }
}

function partition(arr, L, R){
    let less = L -1,
        more = R;
    while(L < more){
        if(arr[L] < arr[R]){
            swap(arr, L++, ++less);
        } else if (arr[L] > arr[R]){
            swap(arr, L, --more);
        } else {
            L++;
        }
    }
    swap(arr, more, R);
    return [less + 1, more];
}
//交换arr[i],arr[j]
function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
//得到两个数之间的随机数
function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min)) + min;
}

let arr = [100,6,10,6,3,5,6,23,9,300,10,5,3,3,1,1,2];
quickSort(arr, 0, arr.length - 1);
console.log(arr);