algorithm - 到位排序

Question

“到位排序”是什么意思？

Answer 1

就地算法的想法并不是排序所独有的，但是排序可能是最重要的情况，或者至少是最著名的情况。这个想法是关于空间效率的-使用最少的RAM，硬盘或其他可以节省的存储空间。这在几十年前的硬件特别受限制的情况下尤其重要。

这个想法是通过连续转换数据直到产生输出，在包含输入的同一存储空间中产生输出。这样避免了使用两次存储的需要-一个区域用于输入，而大小相等的区域用于输出。

排序是一个很明显的例子，因为可以通过重复交换项目来进行排序-排序仅是重新排列项目。交换不是唯一的方法-例如Insertion Sort使用稍微不同的方法，等效于进行一系列交换，但速度更快。

另一个示例是matrix transposition-同样，可以通过交换项目来实现。通过从最低有效数字开始并向上传播进位，也可以就地添加两个非常大的数字(结果替换输入之一)。

回到排序，当您想到punched cards堆栈时，重新安排“就地”的优势变得更加明显-最好避免复制打孔的卡片以对其进行排序。

一些排序算法允许这种形式的就地操作，而另一些则不允许。

但是，所有算法都需要一些额外的存储空间来存储工作变量。如果目标只是简单地通过连续修改输入来产生输出，那么定义通过保留大量内存，使用该内存来产生一些辅助数据结构，然后使用它来指导那些修改的算法就相当容易。您仍然可以通过“原位”转换输入来产生输出，但是您正在打破练习的重点-空间效率不高。

因此，就地定义的常规定义要求您达到某种空间效率标准。绝对 Not Acceptable 使用与输入成比例的额外空间(即O(n)额外空间)，并且仍将算法称为“就地”。

就地算法的Wikipedia page当前声称，就地算法只能使用恒定量的O(1)的额外空间。

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.

In Computational Complexity部分中指定了一些技术，但结论仍然是，例如Quicksort需要O(log n)空间(true)，因此不在原位(我认为这是错误的)。

O(log n)比O(n)小得多-例如，以2为底的对数16,777,216为24。

快速排序和堆排序通常都被认为是就地，并且堆排序可以用O(1)额外的空间来实现(我之前误认为这)。 Mergesort很难就地实现，但异地版本非常易于缓存-我怀疑现实世界的实现会接受O(n)空间开销-RAM便宜，但内存带宽是主要瓶颈，因此，以高速缓存的效率和速度来交换内存通常是一件好事。

[ 编辑在写上面的文章时，我假设我正在考虑数组的就地合并排序。链表的就地合并排序非常简单。关键区别在于合并算法-合并两个链接列表而无需复制或重新分配很容易，使用较大数组的两个子数组(并且没有O(n)辅助存储)进行相同操作AFAIK不是。]

Quicksort即使在原位也具有缓存效率，但是可以通过调用最坏情况的行为而取消其原位算法的资格。在退化的情况下(在非随机版本中，通常在输入已排序时)，运行时为O(n ^ 2)而不是预期的O(n log n)。在这种情况下，额外的空间需求也增加到O(n)。但是，对于大型数据集，并采取一些基本的预防措施(主要是随机选择枢轴选择)，这种最坏情况的行为变得不太可能发生。

我个人的观点是就地算法可以接受O(log n)多余的空间-它不是作弊的，因为它不会破坏就地工作的原始观点。

但是，我的意见当然只是我的意见。

一个额外的注意事项-有时，人们会就地调用一个函数，只是因为该函数在输入和输出上都有一个参数。并不一定意味着该函数具有空间效率，不是通过转换输入来产生结果，也不是参数仍然引用相同的内存区域。这种用法是不正确的(因此 prescriptivists会声明)，尽管它很常见，因此最好注意但不要对此感到压力。