Dan*_*iel 4 sorting algorithm complexity-theory quicksort space-complexity
根据我在维基百科对quicksort空间复杂性的解释中的理解,quicksort的空间复杂性来自其递归性质.我很好奇是否可以非递归地实现快速排序,并且在这样做时,以恒定的空间复杂度实现它.
Gor*_*off 11
维基百科并不总是错的.并且,正如该部分所暗示的那样,有一种方法可以使用恒定空间来执行快速排序或类似的操作.一点很重要.Quicksort本身可以定义为递归分区算法.如果是这样,那么根据定义它将需要O(n)堆栈空间.但是,我假设你没有使用这种迂腐的定义.
只需快速了解分区的工作原理.给定一个数组,一个起点和一个终点,选择一个分区值.然后拆分数组中的数据元素,使得小于分区值的所有内容都在左侧,而更大的内容在右侧.这样做的一个好方法是从每一端开始,找到不属于的第一个值,然后交换它们.顺便说一下,这使用了恒定的空间.
因此,算法的每一步都要经过数组.让我们记住这个事实.
现在,我们可以做一个有趣的观察.如果我们以深度优先的方式进行递归分区,那么我们只需要存储每个范围的端点.在向下的路上,数组的左边缘始终是开始.终点连续接近开头,直到只有两个元素可以交换或不交换.此时,开始移动两个插槽,但我们不知道结束.所以,查看结束并继续该过程.然后在下一步"向上",我们需要下一个终点,依此类推.
问题是:除了将实际值存储在堆栈中之外,我们能通过某种方式找到结束吗？
嗯,答案是肯定的.
递归分区算法中的每个步骤都会读取所有数据.我们可以对数据进行一些额外的计算.特别是,我们可以计算出最大值和第二大值.(我也会计算最小值,但这是一个优化.).
我们对这些值的处理是标记范围.在第一次拆分时,这意味着将第二大值放在拆分点,将最大值放在范围的末尾.在返回树的路上,您知道范围的开始位置.范围的结尾是大于该值的第一个值.
瞧!您可以向上移动"递归"树而不存储任何数据.您只是使用所显示的数据.
完成此操作后,您只需将算法从递归算法更改为while循环.while循环重新排列数据,在每一步设置起点和停止点.它选择一个分离器,分割数据,标记起点和终点,然后在数据的左侧重复.
当它达到最小单位时,它会检查它是否完成(它是否已到达数据的末尾).如果没有,它会查看一个单位的数据点以找到第一个标记.然后它通过数据来寻找终点.顺便说一下,这种搜索在数据分区的复杂性上是等价的,因此它不会增加复杂性的顺序.然后迭代遍历此数组,继续该过程直到完成.
如果数据中有重复项,则过程稍微复杂一些.但是,如果有log(N)重复,我几乎会争论删除重复项,使用剩余的插槽作为堆栈对数据进行排序,然后将它们合并回来.
为什么这是快速排序.快速排序算法是分区交换算法.该算法通过选择分割器值,在两侧划分数据并重复该过程来进行.正如杰弗里在答案中指出的那样,递归是没有必要的.这是一个很大的便利.
该算法以完全相同的方式进行.分区遵循相同的基础规则,左侧记录较小,右侧记录较大.唯一的区别是在每个分区中,特定值被选择在分区的边缘.通过仔细放置这些值,不需要额外的"每步"存储.由于这些值属于分区,因此根据partition-and-repeat的快速排序主体,这是一个有效的分区.
如果有人认为快速排序必须使用递归,那么这将无法通过严格的测试(并且原始问题的答案是微不足道的).
完全有可能以非递归方式实现它，但是您可以通过实现与普通函数调用/返回堆栈分开的堆栈来实现这一点。它可以通过仅存储基本信息而不是大量（大部分相同）函数返回地址来节省一些空间，但其大小仍然是对数的，而不是恒定的。
由于已经讨论过（例如）@Gordon Linoff 在他的回答中引用的算法是否真的是快速排序，我将参考 CAR Hoare 描述快速排序的论文，在我看来，这似乎是关于什么是或正在做什么的最权威的来源不构成快速排序。根据他的论文：
同时，必须存储推迟段的第一项和最后一项的地址。
虽然存储（或多或少）相当于地址（例如索引）而不是实际索引的东西并不算太大，但在我看来，当算法的描述直接指出您必须存储地址，一种不存储地址或任何大致相当于地址的算法，不再是同一算法的实现。
https://academic.oup.com/comjnl/article/5/1/10/395338