SOURCE

function quickSort(arr) {
  // 先复制一下防止后面更改了原数组
  const array = [...arr]

  // 如果只剩小于一个元素,直接返回
  if (array.length <= 1) {
    return array
  }

  const leftArray = []
  const rightArray = []

  // 1. 选择基准元素(简单就取第一个,一点点改进就是用下面随机的)
  // const pivot = array.shift()

  const pivotIndex = Math.floor(Math.random() * array.length)
  const pivot = array.splice(pivotIndex, 1)

  // 2. 循环取出直到空,小的放左边,大于等于的放右边
  while (array.length) {
    const current = array.shift()

    if (current < pivot) {
      leftArray.push(current)
    } else {
      rightArray.push(current)
    }
  }

  // 3. 分别对左边数组和右边数组递归排序,最后合并结果
  return quickSort(leftArray).concat([pivot], quickSort(rightArray))
}

const arr = [2, 3, 41, 1, 6, 53, 4, 6, 87, 4]

const res = quickSort(arr)

console.log('res', res)