arrays - 通过在前端或末尾插入来对数组进行排序

Question

如果只允许删除元素并将它们放在数组的前面或后面，你将如何对整数数组进行排序？我认为考虑这个问题的一种简单方法是根据双端队列，但我不确定什么是最有效的算法。

如果我要选择最大的元素，把它放在最前面，然后选择第二大的元素，把它放在最前面，重复……时间复杂度是O(n^2)。解决此问题的更好方法是什么？

您不一定需要使用数组，它也可以是 arrayList(这听起来更好，因为插入前面或后面不会涉及移动所有内容。

谢谢!这不是为了家庭作业，只是出于好奇!

Answer 1

实际上，您可以仅使用这些操作进行归并排序。

考虑合并排序链表的工作原理。您创建一个空链表作为目的地。然后比较源列表中的前两项并将它们按顺序添加到目标列表中(即最低的优先)。您对列表中的每对项目继续该操作。

完成比较相邻项目后，目标列表现在成为源列表，您合并项目 1、2、3、4，然后是项目 5、6、7、8 等。

你可以只用一个链表做同样的事情。如果您知道列表中有多少项目(最坏的情况，遍历它并计算它们)，那么您的输出列表就是列表中最后一个节点之后的项目。因此，您比较前两项并将它们按顺序移动到列表的末尾。重复直到列表排序。

用数组做这件事当然会非常昂贵，因为你会不断地向上移动，以便在最后腾出空间。但是你可以用 ArrayList 来做到这一点(在 Java 中)或 List<T> (在 C# 中)只需将列表的大小加倍即可。您必须跟踪目标索引(第一次迭代为 Count，下一次迭代为 0，等等)，完成后您可能必须将最终项目移到列表的前面(如果您进行了奇数次迭代)。而且，当然，您必须在返回之前删除所有多余的项目。但这是可以做到的。

如果您使用的是 ArrayList，则复杂度为 O(n log n) 时间和 O(n) 额外空间。 O(1) 额外空间，如果您使用链表进行操作。