javascript - 是就地排序吗？

Question

我已阅读 Nicholas C. Zakas 发布的博客(原始链接:Computer science in JavaScript: Merge sort)。有一个问题一直困扰着我。

博客通过JavaScript解释了归并排序的概念，作者给出了归并排序的两种解决方案(第一种是非原地，另一种是)。

我的问题是:我认为方案一和方案二在空间复杂度上没有区别，所以应该理解所谓的“就地排序”只是输入输出是否是在这种情况下是相同的数组，但与额外的空间无关？

代码如下:

解决方案一(非就地排序):

function mergeSort(items) {
  // Terminal case: 0 or 1 item arrays don't need sorting
  if (items.length < 2) {
    return items;
  }
  var middle = Math.floor(items.length / 2),
      left = items.slice(0, middle),
      right = items.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

方案二(就地排序):

function mergeSort(items) {
  if (items.length < 2) {
    return items;
  }
  var middle = Math.floor(items.length / 2),
      left = items.slice(0, middle),
      right = items.slice(middle),
      params = merge(mergeSort(left), mergeSort(right));
  // Add the arguments to replace everything between 0 and last item in the array
  params.unshift(0, items.length);
  items.splice.apply(items, params);
  return items;
}

两者使用相同的函数merge:

function merge(left, right){
  var result = [],
      il = 0,
      ir = 0;
  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  return result.concat(left.slice(il)).concat(right.slice(ir));
}

Answer 1

是的，这两种算法都在一个新的、不同的数组中对数据进行排序。这意味着需要 O(n) 额外空间。

唯一的区别是所谓的“就地排序”然后清空原始数组并用排序后的数据填充它。这是否使其就地取决于 in-place 的定义。

An in-place algorithm is an algorithm which transforms input using a data structure with a small amount of extra storage space.

In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, though sometimes anything in o(n) is allowed.

所以通常它不被认为是就地的，因为额外的空间复杂度超过o(n)。

如果你想要一个O(n log(n))时间复杂度和O(1)额外空间复杂度的就地排序算法，你可以使用heapsort .缺点是，与归并排序不同，堆排序不是 stable。