javascript - 在有或没有 pop 和 shift 的情况下，javascript 中的快速排序更快吗

Question

我正在关注一些有关 javascript 算法的视频，发现讲师使用类似以下代码的内容实现了快速排序:

function quickSort(arr){
  if(arr.length <= 1) return arr
  const pivot = arr[arr.length - 1]
  let left = []
  let right = []
  for(let i = 0; i < arr.length-1; i++){
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return [].concat(quickSort(left),pivot,quickSort(right))
}

当我编写自己的版本时，我没有使用 for 循环并不必担心忽略枢轴或有冗长的 for 循环，而是使用了 pop 和 shift，如下所示:

function quickSort(arr){
  if(arr.length <= 1) return arr
  const pivot = arr.pop()
  let left = []
  let right = []
  while(arr[0]){
    if (arr[0] < pivot) {
      left.push(arr.shift())
    } else {
      right.push(arr.shift())
    }
  }
  return [].concat(quickSort(left),pivot,quickSort(right))
}

视频的评论(youtube)说我的版本很糟糕，但没有给出进一步的解释。我不确定我应该在谷歌中搜索什么。据我所知，这两种情况都一样快。有人可以告诉我使用 pop 或 shift 的问题吗？

Answer 1

Can someone tell me the issue with using pop or shift?

我认为问题是使用 pop 和/或 shift 修改输入数组比简单地从中读取元素更昂贵。特别是每次转变都可能并且可能确实花费O(N)，尽管原则上这取决于实现。

请注意，插入新的每分区数组也可能会产生一些不必要的成本。至少，它比传统的快速排序实现会产生更多的内存开销，传统的快速排序实现会对输入数组进行就地排序。