思路

（1）从数组中选择一个值作为主元，

（2）进行划分操作，使得
比主元小的值都排在主元之前
比主元大的值都排在主元之后，

（3）对划分后的小数组重复之前的两个步骤，直至数组完全排序

实现

quickSort

function quickSort(array) {
    return quick(array, 0, array.length - 1);
}

quick

function quick(array, left, right) {
    let index;
    if (array.length > 1) {
        index = partition(array, left, right);
        if (left < index - 1) { // 存在左子数组
            quick(array, left, index - 1);
        }
        if (index < right) { // 存在右子数组
            quick(array, index, right);
        }
    }
    return array;
}

partition

function partition(array, left, right) {
    const index = Math.floor(Math.random() * (right - left + 1) + left),
        pivot = array[index];
    let i = left,
        j = right;
    while (i <= j) {
        while (array[i] <= pivot) {
            i++;
        }
        while (array[i] >= pivot) {
            j--;
        }
        if (i <= j) {
            [array[i], array[j]] = [array[j], array[i]];
            i++;
            j--;
        }
    }
    return i;
}