快排

const _quickSort = (array) => {
  // 补全代码
  myQuickSort(array, 0, array.length - 1);
  return array;
};
// 启动函数

// 重点
function myQuickSort(array, l, r) {
  if (l < r) {
    let index = partition(array, l, r); //进行一轮快排
    myQuickSort(array, l, index - 1);
    myQuickSort(array, index + 1, r);
  }
}
function partition(array, l, r) {
  // 随机l-r取值
  let pivot = array[Math.floor(Math.random() * (r - l + 1)) + l];
  // *****这里是双重循环
  while (l < r) {
    while (array[l] < pivot) l++;
    while (array[r] > pivot) r--;
    // 此时其实都等于pivot
    // 当数组中存在重复数据时，即都为pivot，但位置不同
    // 继续递增i，防止死循环
    if (l !== r && array[l] === array[r]) l++;
    else if (l < r) {
      //此时array[l]>pivot,array[r]<pivot (=的情况已经排除)
      [array[l], array[r]] = [array[r], array[l]];
    }
  }
  //此时l==r
  return l;
}