algorithm - 是否可以实现 O(1) 空间复杂度的快速排序？

Question

从我在维基百科对快速排序空间复杂度的解释中了解到，快速排序的空间复杂度来自于它的递归性质。我很好奇是否有可能以非递归方式实现快速排序，并且在这样做的过程中，以恒定的空间复杂度实现它。

Answer 1

维基百科并不总是错误的。而且，正如该部分所建议的，有一种方法可以使用常量空间进行快速排序或类似的操作。重要的一点。快速排序本身可以定义为递归分区算法。如果是这样，那么根据定义，它将需要 O(n) 堆栈空间。但是，我假设您没有使用这种迂腐的定义。

只是快速回顾一下分区是如何工作的。给定一个数组、一个起点和一个终点，选择一个分区值。然后拆分数组中的数据元素，因此小于分区值的所有内容都在左侧，而大于分区值的所有内容都在右侧。这样做的一个好方法是从每一端开始，找到第一个不属于的值，然后交换它们。顺便说一下，这使用了常量空间。

因此，算法的每一步都在遍历数组。让我们记住这个事实。

现在，我们可以做一个有趣的观察。如果我们以深度优先的方式进行递归分区，那么我们只需要存储每个范围的端点。在下降的过程中，数组的左边缘始终是开始。终点逐渐接近起点，直到只有两个可以交换的元素。此时，开始移动了两个槽，但我们不知道结束。因此，查找结尾并继续该过程。然后在下一步“向上”中，我们需要下一个端点，以此类推。

问题是：除了将实际值存储在堆栈中之外，我们还能通过其他方式找到终点吗？

嗯，答案是“是”。

递归分区算法中的每一步都会读取所有数据。我们可以对数据做一些额外的计算。特别是，我们可以计算最大值和第二大值。（我也会计算最小值，但这是一种优化。）。

我们对值所做的是标记范围。在第一次拆分时，这意味着将第二个最大值放在拆分点，将最大值放在范围的末尾。在返回树的路上，你知道范围从哪里开始。范围的结尾是第一个大于该值的值。

瞧！您可以在不存储任何数据的情况下向上移动“递归”树。您只是使用所提供的数据。

完成此操作后，您只需将算法从递归算法更改为 while 循环。while 循环重新排列数据，在每一步设置起点和终点。它选择一个拆分器，拆分数据，标记起点和终点，然后在数据的左侧重复。

当它下降到最小单位时，它会检查它是否完成（它是否到达数据的末尾）。如果不是，它会查看一个单位的数据点以找到第一个标记。然后它通过数据寻找终点。顺便说一下，这种搜索在复杂性上等同于数据的分区，因此它不会增加复杂性的顺序。然后它遍历这个数组，继续这个过程直到它完成。

如果数据中有重复项，则该过程会稍微复杂一些。但是，如果有 log(N) 重复项，我几乎会主张删除重复项，使用剩余的插槽作为堆栈对数据进行排序，然后将它们重新合并。

为什么这是快速排序。快速排序算法是一种分区交换算法。该算法通过选择一个拆分器值、在两侧划分数据并重复此过程来进行。正如杰弗里在他的回答中指出的那样，递归不是必需的。这是一个很大的方便。

该算法以完全相同的方式进行。分区遵循相同的基本规则，左侧记录较小，右侧记录较大。唯一的区别是在每个分区内，特定的值被选择在分区的边缘。通过仔细放置这些值，不需要额外的“每步”存储。由于这些值属于分区，因此根据分区和重复的快速排序原则，这是一个有效的分区。

如果有人争辩说快速排序必须使用递归，那么这将无法通过严格的测试（并且原始问题的答案是微不足道的）。

Answer 2

完全有可能以非递归方式实现它，但是您可以通过实现与正常函数调用/返回堆栈分开的堆栈来实现。它可以通过只存储基本信息而不是大量（大部分相同的）函数返回地址来节省一些空间，但它的大小仍然是对数的，而不是恒定的。

Answer 3

Branislav Ďurian 在 1986 年提出了 Quicksort 的恒定空间版本。参见他的论文“Quicksort without a stack”。在 J. Gruska、B. Rovan 和 J. Wiedermann，编辑，计算机科学数学基础论文集，计算机科学讲义第 233 卷，第 283-289 页。施普林格出版社，1986 年。

其他几位作者对此进行了跟进。你可以找 Bing-Chao 和 Knuth (1986)；韦格纳（1987）；Kaldewaij 和 Udding（1991 年）；格里斯 (1994)。