Javascript + Quicksort:这个维基百科实现是如何工作的

Javascript + Quicksort: how does this wikipedia implementation work?

本文关键字：百科 实现 何工作 工作 Quicksort Javascript      更新时间：2023-09-26

我正在尝试提升我的javascript+算法游戏。我正在维基百科上查看这个快速排序实现：http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#JavaScript

function qsort(a) {
  if (a.length == 0) return [];
  var left = [], right = [], pivot = a[0];
  for (var i = 1; i < a.length; i++) {
    a[i] < pivot ? left.push(a[i]) : right.push(a[i]);
  }
  return qsort(left).concat(pivot, qsort(right));
}

我理解这个概念。它以递归方式将原始数组分解为较小的部分，并对较小的数组进行排序。但是，当它从不返回左/右数组（类似于 return leftArrayResult;）时，我看不出这个 qsort 函数是如何工作的。这是否意味着 qsort 总是返回null或空数组？所以qsort(left).concat(pivot, qsort(right)总是null.concat(pivot, null)，因此永远不会起作用？

如果我们有未排序的[6,10,4,1]，

第一阶段：

qsort[6,10,4,1];

pivot = 6;

在 for 循环中，循环的每个通道都进行了编号：

  1. 10 > 6 ，添加到右侧数组
  2. 4 < 6 ，添加到左侧数组
  3. 1 < 6 ，添加到左侧数组

left = [4,1]; right = [10]; pivot = 6;

然后再次在左侧数组上递归调用 qsort，该数组[4,1] 。

第二阶段：

pivot = 4

在 for 循环中，循环的每个通道都进行了编号：

  1. 1 < 4 ，添加到左侧数组

left = [1]; right = []; pivot = 4;

然后递归调用 qsort，并在左侧数组上再次调用，该数组[1] 。

第三阶段：

pivot = 1

不执行 for 循环。

left = []; right = []; pivot = 1;

qsort 在左侧数组中调用。

第四阶段：

这次 qsort 返回一个空数组。

执行现在移动到第三个堆栈中的 concat 调用，获取空数组并将其连接到 1 和 qsort(right) 的结果，这也将返回一个空数组。所以现在返回的值是 [1] 。

执行现在返回到第二阶段，其中 [1] 连接到 4 的枢轴和 qsort([]) 的结果，因此我们现在的返回值为 [1,4] 。

执行现在返回到第一阶段，因此我们将[1,4]的结果连接到 6 的枢轴和 qsort([10]) 的结果，以获得 [1,4,6,10] 的结果。

我希望这很容易理解！

相关文章：