就地排序

Question

就地排序

algorithmsorting

37

"sort in place"的意思是就地排序。

- joker

它们是不可比较的：原地排序 是一种排序算法的特征，自然排序 指的是您希望对集合进行排序的顺序。因此，您可以使用自然排序来进行原地排序。 - assylias

在一般语义中，“in-place”的意思是指在原地进行操作。这里有更多相关信息。 - RBT

5个回答

6

原地排序是指在排序过程中不需要任何额外的空间。根据维基百科所述，它表示

原地算法是一种使用数据结构进行输入转换的算法，该算法只需要少量、恒定的额外存储空间。

快速排序是原地排序的一个例子。

- roger_that

1

@cmbaxter - O(log n)的空间比O(n)的空间好得多，这是关键点。少量并不一定是恒定的量。非原地算法会在保留旧副本的同时生成一个新副本。需要O(n)空间的算法被视为不原地，因为使用O(n)空间仅用于弄清如何进行交换被认为是欺骗（失去意义）。 - user180247

1

一定要爱维基百科。《原地排序》文章指出，快速排序不是原地排序，因为它没有使用固定大小的数据结构。但是如果你阅读《快速排序》文章，它说可以通过原地排序来实现。难怪会有这样的混淆 :) - cmbaxter

1

@Steve314，在链表上进行归并排序可以使用O(1)空间和O(n log n)时间，只要您将链接视为原始对象的一部分。 - Mark Ransom

1

@Steve314 堆排序可以使用迭代法完成，不需要使用栈。 - pjs

1

@Steve314，这与堆栈无关。合并通过将项目从一个列表移动到另一个列表来完成，您可以通过更改链接而不使用任何额外空间来完成此操作。唯一需要跟踪的是一个列表结束和另一个列表开始的位置，您可以通过单个变量告诉您列表的长度来完成这个任务（因为除了最后一个列表外，所有列表的长度都相同）。 - Mark Ransom

显示剩余7条评论

4

我认为这些术语并不密切相关： 原地排序指通过直接修改列表元素顺序来对现有列表进行排序。相反，是将原始列表保持不变，并创建一个按顺序排列的新列表。 自然排序是一个用于描述如何对完整对象进行排序的术语。例如，您可以说 0比1低（整数的自然排序）或在字母表顺序中 A在B之前（字符串的自然排序）。然而，通常很难说Bob 一般来说比Alice更大或更小，因为这严重取决于具体属性（按姓名字母顺序，按年龄，按收入等）。因此，人没有自然排序。

- Matthias Meid

我同意你的评论，但维基百科说：“原地算法是一种使用数据结构进行输入转换的算法，该数据结构只需要少量且恒定的额外存储空间。” - spandey

0

可以通过使用交换函数来完成，而不是创建一个全新的结构体，我们甚至不知道该算法的名称就能实现它 :D

- Mostafa Sultan

0

我不确定这些概念是否足够相似，可以像建议的那样进行比较。是的，它们都涉及排序，但一个是关于人类可理解（自然）的排序顺序，而另一个则定义了一种算法，通过覆盖现有结构来实现高效排序，而不是使用额外的数据结构（如冒泡排序）。

- cmbaxter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user180247 · Accepted Answer

在编程中，就地算法的概念并不只适用于排序，但排序可能是最重要的情况，或者至少是最为人所知的情况。这个想法关乎空间效率——使用尽可能少的RAM、硬盘或其他存储器。几十年前，硬件资源非常有限，这一点尤为重要。

该想法是通过连续转换数据以生成输出，而使用包含输入的相同内存空间。这避免了使用两倍的存储空间——一个区域用于输入，一个等大的区域用于输出。

排序是一个相当明显的例子，因为排序可以通过重复交换项来完成——排序只是重新排列项。交换不是唯一的方法——例如，插入排序使用稍微不同的方法，它等效于做一系列交换但更快。

另一个例子是矩阵转置——同样，这可以通过交换项来实现。通过从最低有效数字开始传递进位，也可以在原地（结果替换其中一个输入）添加两个非常大的数字。

回到排序问题，如果考虑到一堆打孔卡片，通过重新排列“原地”避免复制打孔卡片进行排序会更好。

一些排序算法支持这种原地操作方式，而其他算法则不支持。

然而，所有算法都需要一些额外的存储空间来存储工作变量。如果目标仅是通过连续修改输入来生成输出，那么可以通过保留大块内存来定义这样的算法，使用它来产生一些辅助数据结构，然后使用它来指导这些修改。你仍然是通过在原地转换输入来生成输出，但你正在破坏整个练习的意义——你没有节省空间。

因此，原地定义的正常定义要求您达到一定的空间效率标准。使用与输入成比例的额外空间（即O(n)额外空间）并仍将您的算法称为“原地”是绝对不可接受的。

维基百科页面上关于原地算法的描述称，一个原地算法只能使用常数级别（O(1)）的额外空间。

在计算机科学中，原地算法（或拉丁语中的in situ）是一种使用具有小型、恒定数量的额外存储空间的数据结构来转换输入的算法。

在计算复杂性部分中有一些技术细节，但结论仍然是例如快速排序需要O(log n)的空间（正确），因此不是原地的（我认为是错误的）。

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

快速排序和堆排序通常被认为是就地排序，而堆排序可以用O(1)的额外空间实现（我之前对此有误）。归并排序更难以就地实现，但是其非就地版本非常适合缓存 - 我怀疑实际实现接受O(n)的空间开销 - 内存便宜但内存带宽是主要瓶颈，因此将内存换成缓存效率和速度通常是一个不错的选择。【注：在上述内容中，我假设了数组的就地归并排序。链表的就地归并排序非常简单。关键区别在于合并算法 - 对两个没有复制或重新分配的链接列表进行合并很容易，但是在不使用O(n)辅助存储器的情况下对更大数组的两个子数组执行相同操作的AFAIK不行】

快速排序算法即使是就地排序，也具有高缓存效率，但由于其最坏情况的行为，可能会被取消作为就地算法。在退化情况下（通常是输入已经排序的非随机版本），运行时间为O(n^2)，而不是预期的O(n log n)。在这种情况下，额外的空间需求也增加到了O(n)。然而，对于大型数据集并采取一些基本预防措施（主要是随机选择枢轴），这种最坏情况的行为变得极不可能发生。

我个人认为，在就地算法中，O(log n)的额外空间是可以接受的 - 这不是作弊，因为它没有违反就地工作的原始目的。

然而，我的观点当然只是我的观点。

还有一个额外的注意事项 - 有时候，人们会将一个函数称为就地函数，仅仅是因为它有一个参数既用于输入也用于输出。这并不一定意味着该函数是空间高效的，结果是通过转换输入产生的，甚至该参数仍然引用同一内存区域。这种用法不正确（规范主义者会这样说），尽管它很常见，最好是意识到它但不要过于担心。