排序到位 [英] Sorting in place
问题描述
什么叫为之类的地方？
推荐答案
的原地算法的想法是不是唯一的排序，但排序可能是最重要的情况下，或至少是最知名的。这个想法是关于空间效率 - 使用的内存，硬盘或其他存储，您可以逃脱的最低金额。这是特别重要回去几十年，当硬件是非常有限。
The idea of an in-place algorithm isn't unique to sorting, but sorting is probably the most important case, or at least the most well-known. The idea is about space efficiency - using the minimum amount of RAM, hard disk or other storage that you can get away with. This was especially relevant going back a few decades, when hardware was much more limited.
我们的想法是，以产生在包含输入通过连续地变换该数据，直到输出产生相同的内存空间的输出。这避免了需要使用的存储两次。 - 一个区域用于输入和一个大小相等的区域为输出
The idea is to produce an output in the same memory space that contains the input by successively transforming that data until the output is produced. This avoids the need to use twice the storage - one area for the input and an equal-sized area for the output.
排序是一个相当明显的情况下，对于这一点，因为排序可以通过多次交换项目来完成 - 分拣只能重新安排项目。交流是不是唯一的方法 - 在插入排序的，例如，使用一个稍微不同的方式，相当于做了运行交往，但速度更快。
Sorting is a fairly obvious case for this because sorting can be done by repeatedly exchanging items - sorting only re-arranges items. Exchanges aren't the only approach - the Insertion Sort, for example, uses a slightly different approach which is equivalent to doing a run of exchanges but faster.
又如矩阵转 - 再次，这可以通过交换物品来实现。增加两个非常大的数字，也可以就地通过启动在至少显著位和propogating完成（结果替换的输入之一）承载向上
Another example is matrix transposition - again, this can be implemented by exchanging items. Adding two very large numbers can also be done in-place (the result replacing one of the inputs) by starting at the least significant digit and propogating carries upwards.
再回到整理的优势，以重新安排到位当你觉得栈的获得更明显的穿孔卡片 - 这是preferable避免复制打孔卡只对它们进行排序
Getting back to sorting, the advantages to re-arranging "in place" get even more obvious when you think of stacks of punched cards - it's preferable to avoid copying punched cards just to sort them.
有些算法进行排序允许这种风格的就地操作，而不用。
Some algorithms for sorting allow this style of in-place operation whereas don't.
然而，所有的算法需要的部分的额外存储工作变量。如果目标是简单地通过连续修改输入以产生输出，这也很容易以限定那些，通过保留的存储器大块，使用以产生一些辅助的数据结构，然后使用该引导这些修改的算法。你还在产生输出转化到位的投入，但你击败行使整点 - 你是不是节省空间的
However, all algorithms require some additional storage for working variables. If the goal is simply to produce the output by successively modifying the input, it's fairly easy to define algorithms that do that by reserving a huge chunk of memory, using that to produce some auxiliary data structure, then using that to guide those modifications. You're still producing the output by transforming the input "in place", but you're defeating the whole point of the exercise - you're not being space-efficient.
有关该原因，就地定义的标准清晰度要求您实现空间效率一些标准。这是绝对不能接受的使用额外的空间正比于输入（即，O（n）的额外空间），仍然打电话给你的算法就地。
For that reason, the normal definition of an in-place definition requires that you achieve some standard of space efficiency. It's absolutely not acceptable to use extra space proportional to the input (that is, O(n) extra space) and still call your algorithm "in-place".
借助维基百科页面上就地算法，目前声称，就地算法只能用一个常数量 - O（1） - 额外的空间
The Wikipedia page on in-place algorithms currently claims that an in-place algorithm can only use a constant amount - O(1) - of extra space.
在计算机科学中，就地算法（或在拉丁原位）是一种算法，使用数据结构的额外的存储空间小，恒定量，其将输入
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.
有在计算复杂性部分规定了一些技术性问题，但结论仍是如快速排序需要O（log n）的空间（真），因此不能就地（我相信这是假的）。
There are some technicalities specified in the In Computational Complexity section, but the conclusion is still that e.g. Quicksort requires O(log n) space (true) and therefore is not in-place (which I believe is false).
为O（log n）的多的为O小（N） - 例如基地2个对数16,777,216为24
O(log n) is much smaller than O(n) - for example the base 2 log of 16,777,216 is 24.
快速排序和堆排序都通常被认为是就地，和堆排序可以用O（1）额外的空间来实现（我错了这个更早）。归并是比较困难的就地实现，但超出地方的版本是非常缓存友好 - 我怀疑现实世界中实现接受O（n）的空间开销 - RAM是便宜，但内存带宽是一大瓶颈，所以对于高速缓存的效率和速度买卖内存往往是一个很好的协议。
Quicksort and heapsort are both normally considered in-place, and heapsort can be implemented with O(1) extra space (I was mistaken about this earlier). Mergesort is more difficult to implement in-place, but the out-of-place version is very cache-friendly - I suspect real-world implementations accept the O(n) space overhead - RAM is cheap but memory bandwidth is a major bottleneck, so trading memory for cache-efficiency and speed is often a good deal.
快速排序也是缓存效率，即使是在就地，但可被取消资格作为一个原地算法通过吸引其最坏情况下的行为。有一种退化情况（在一非随机版本，通常当输入已经排序），其中运行时间为O（n ^ 2），而不是预期为O（n log n）的。在这种情况下，额外的空间需求也提高到为O（n）。但是，对于大型数据集和一些基本的precautions（主要是随机支点选择）这种最坏情况下的行为变得荒谬的可能性不大。
Quicksort is also cache-efficient, even in-place, but can be disqualified as an in-place algorithm by appealing to its worst-case behaviour. There is a degenerate case (in a non-randomized version, typically when the input is already sorted) where the run-time is O(n^2) rather than the expected O(n log n). In this case the extra space requirement is also increased to O(n). However, for large datasets and with some basic precautions (mainly randomized pivot selection) this worst-case behaviour becomes absurdly unlikely.
我个人的看法是，O（log n）的额外的空间是可以接受的就地算法 - 这不是欺骗，因为它没有打败就地工作的原点
My personal view is that O(log n) extra space is acceptable for in-place algorithms - it's not cheating as it doesn't defeat the original point of working in-place.
不过，我的看法是当然只是我的意见的。
However, my opinion is of course just my opinion.
一个额外注 - 有时，人们会叫就地功能，只是因为它具有输入和输出的参数。这并不一定意味着该功能是节省空间，这个结果是通过将输入产生的，甚至可以说参数仍引用相同的内存区域。这种用法是不正确的（左右 prescriptivists 会声称），虽然它是相当普及了这是最好的了解，但没有得到强调一下吧。
One extra note - sometimes, people will call a function in-place simply because it has a single parameter for both the input and the output. It doesn't necessarily follow that the function was space efficient, that the result was produced by transforming the input, or even that the parameter still references the same area of memory. This usage isn't correct (or so the prescriptivists will claim), though it's common enough that it's best to be aware but not get stressed about it.
这篇关于排序到位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
