arrays - 顺序排序算法

Question

我想对顺序进入的元素进行排序，即我希望在下一个元素进入之前对我的向量进行排序。我知道插入排序的复杂度为 n^2，如果我总共有 n 个元素。合并排序应该更好。然而，人们常说归并排序的复杂度为 n log n；但我想如果你要一次对 n 个元素进行排序，那是正确的。相反，如果它们一个接一个地出现，并且您需要对临时向量进行排序，则复杂度会上升到\sum_{i=2}^n i log(i)。这仍然小于我假设的 n^2，但肯定大于 n log n。

对吗？

谢谢

Answer 1

编辑 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²)。