“就地排序”是什么意思？
问问题
43948 次
5 回答
42
就地算法的想法并不是排序所独有的，但排序可能是最重要的情况，或者至少是最知名的情况。这个想法是关于空间效率的——使用最少数量的 RAM、硬盘或其他您可以摆脱的存储空间。这在几十年前尤其重要，当时硬件更加有限。
这个想法是通过连续转换数据直到产生输出，在包含输入的相同存储空间中产生输出。这避免了使用两倍存储空间的需要——一个区域用于输入，一个相同大小的区域用于输出。
排序是一个相当明显的例子，因为排序可以通过重复交换项目来完成 - 排序只会重新排列项目。交换不是唯一的方法——例如，插入排序使用一种稍微不同的方法，相当于进行一系列交换，但速度更快。
另一个例子是矩阵转置——同样，这可以通过交换项目来实现。添加两个非常大的数字也可以通过从最低有效数字开始并向上传播来就地完成（结果替换其中一个输入）。
回到排序，当您想到成堆的打孔卡片时，“就地”重新排列的优势变得更加明显- 最好避免复制打孔卡片只是为了对它们进行排序。
一些排序算法允许这种就地操作，而另一些则不允许。
但是，所有算法都需要一些额外的存储空间来存储工作变量。如果目标只是通过连续修改输入来产生输出，那么通过保留大量内存来定义算法是相当容易的，使用它来产生一些辅助数据结构，然后使用它来指导这些修改。您仍然通过“就地”转换输入来产生输出，但是您正在挫败练习的全部要点-您没有节省空间。
因此，就地定义的正常定义要求您达到某种空间效率标准。使用与输入成比例的额外空间（即 O(n) 额外空间）并且仍然将您的算法称为“就地”是绝对不可接受的。
就地算法的维基百科页面目前声称就地算法只能使用恒定数量 - O(1) - 的额外空间。
在计算机科学中，就地算法（或拉丁语原位）是一种算法，它使用具有少量、恒定数量的额外存储空间的数据结构来转换输入。
在计算复杂性部分中指定了一些技术细节，但结论仍然是，例如快速排序需要 O(log n) 空间（真），因此不是就地（我认为这是错误的）。
O(log n)远小于 O(n) - 例如 16,777,216 的以 2 为底的对数是 24。
快速排序和堆排序通常都被认为是就地排序，并且可以使用 O(1) 额外空间来实现堆排序（我之前对此有误）。Mergesort 更难就地实现，但非就地版本对缓存非常友好——我怀疑现实世界的实现会接受 O(n) 空间开销——RAM 很便宜，但内存带宽是主要瓶颈，因此，用内存换取缓存效率和速度通常是一笔划算的交易。
[编辑当我写上面的内容时，我假设我正在考虑对数组进行就地合并排序。链表的就地合并排序非常简单。关键区别在于合并算法 - 合并两个链表而不复制或重新分配很容易，对更大数组的两个子数组（并且没有 O(n) 辅助存储）做同样的事情 AFAIK 不是.]
快速排序也是高效缓存的，即使是就地的，但由于诉诸其最坏情况的行为，可能会被取消为就地算法的资格。有一个退化的情况（在非随机版本中，通常当输入已经排序时），运行时间是 O(n^2) 而不是预期的 O(n log n)。在这种情况下，额外的空间需求也增加到 O(n)。然而，对于大型数据集和一些基本的预防措施（主要是随机枢轴选择），这种最坏情况的行为变得荒谬可笑。
我个人的观点是，O(log n) 额外空间对于就地算法是可以接受的——这不是作弊，因为它不会破坏就地工作的原始点。
但是，我的意见当然只是我的意见。
一个额外的注意 - 有时，人们会就地调用一个函数，因为它对输入和输出都有一个参数。这并不一定意味着该函数是节省空间的，结果是通过转换输入产生的，或者甚至参数仍然引用相同的内存区域。这种用法是不正确的（或者规范主义者会声称），尽管它很常见，最好注意但不要为此感到压力。
于 2013-05-16T18:03:03.257 回答
4
我不认为这些术语密切相关：
就地排序意味着通过直接在列表中修改元素顺序来对现有列表进行排序。相反的是保留原始列表并按顺序创建一个包含元素的新列表。
自然排序是描述如何以某种方式对完整对象进行排序的术语。例如，您可以说0 低于 1（整数的自然排序）或A按字母顺序排在 B 之前（字符串的自然排序）。虽然你很难说 Bob 通常比 Alice 大或小，因为它在很大程度上取决于特定属性（按字母顺序按姓名、年龄、收入……）。因此，人们没有自然的顺序。
于 2013-05-16T10:57:55.953 回答
0
我不确定这些概念是否足够相似，可以按照建议进行比较。是的，它们都涉及排序，但一个是关于人类可以理解（自然）的排序排序，另一个定义了一种算法，通过覆盖现有结构而不是使用额外的数据结构（如冒泡排序）
于 2013-05-16T10:59:08.490 回答
0
它可以通过使用交换函数来完成，而不是制作一个全新的结构，我们甚至不知道它的名字就实现了该算法：D
于 2015-05-16T18:31:55.453 回答