顺序排序算法

Question

我希望对顺序到来的元素进行排序，也就是说，在下一个元素进入之前，我希望我的向量已经排序好了。我知道插入排序的复杂度为n^2，如果我有总计n个元素。归并排序应该更好一些。然而，通常会说归并排序的复杂度为n log n；但是我猜想，如果你要逐个地排序n个元素，并且需要将临时向量排序，那么复杂度会上升到\sum_{i=2}^n i log(i)。我想这仍然比n^2要小，但绝对比n log n大。

我说得对吗？

谢谢。

- Bob

Answer 1

EDIT 2:

\sum_{i=1}^N i log i > \sum_{i=1}^N i = O(N²)

编辑：显然，你没有理解重点，所以我会尝试澄清。

首先，在每次插入后确保数组排序的情况下，将N个元素插入到数组中可以在O(N²)的复杂度内完成。您可以使用以下算法来插入一个元素：

• 由于数组已排序，请使用二进制搜索查找要插入元素的位置。需要O(log i)时间，其中i是数组的当前大小。
• 通过将其后面的所有元素向右移动一个位置来插入元素。这涉及移动多达i个元素，因此它是O(i)。

对于N次插入重复使用此算法，从而得到\sum_i (i + log i) = O(N²)。

为了使其非常清楚：这不是插入排序。插入排序将涉及重新插入所有元素以对整个数组进行排序，而此算法仅插入一个元素。

其次，执行此操作不能比O(N²)更快：将一个元素插入到大小为i的数组中并保持数组排序的复杂度大于O(i)，因为它涉及移动多达i个元素。 没有绕过这个基本事实的方法：如果您将1插入到[2,3,..,i]中，则结果为[1,2,3,..,i]，这意味着必须移动元素2、3 .. i 。

因此，总和大于\sum_i i = O(N²)。

- Victor Nicollet

---

如果你在谈论插入排序，每一步都有i个元素在数组中，再加上你想要插入的一个。在最坏的情况下，需要i步才能找到正确的位置。因此，你有\sum_{i=1}^n i = O(n^2)。而使用归并排序则不同，因为你可以将新元素放在向量的前面（或者末尾），复杂度为O(1)，然后对整个向量进行排序。这将给出\sum i log(i)。 - Bob

首先，你假设插入排序内部使用二叉树来获得O(i)，否则在不知道元素统计信息的情况下，最坏的情况需要i步。其次，如果每个步骤都需要O(i)，总共n个步骤，则得到O(1)+O(2)+...+O(n)=O(n^2)。 - Bob

在标准文献中，没有提到二叉树的内部。然而，你所说的复杂度是正确的，最终是O(n^2)，顺便说一下，这就是插入排序的工作原理：每次都执行你所说的操作（查找正确位置并插入元素）。我关于归并排序的错误，因为如果将所有贡献相加，log(i)显然至少是n^2（尽管移动的东西不适用，因为你可以将元素附加到末尾，复杂度为1，或者使用队列在前面插入元素，然后再进行排序）。 - Bob

我说的是内部数组每次都会翻倍。顺便说一句，如果你使用树，甚至不需要数组。此时你将拥有\sum log(i)；问题是，我想保持树的平衡。 - Bob

使用红黑树，最终得到的结果是 \sum log i = n log n。 - Victor Nicollet