顺序排序算法
我想对按顺序进入的元素进行排序，即，我希望在下一个元素进入之前对向量进行排序。如果我总共有 n 个元素，我知道插入排序的复杂度为 n^2。归并排序应该会更好。然而，人们常说归并排序的复杂度为n log n；但我想如果你要一次对 n 个元素进行排序，那就是真的。相反，如果它们一一出现，并且您需要对临时向量进行排序，则复杂性将上升到 \sum_{i=2}^ni log(i)。我认为这仍然小于 n^2，但肯定大于 n log n。
这是正确的吗？
谢谢
I wanted to sort elements that come in sequentially, i.e., I want my vector to be sorted before the next element comes in. I know that insertion sort has complexity n^2, if I have a total of n elements. Merge sort should be better. However, it is often said that merge sort has complexity n log n; but I guess that is true if you are going to sort n elements at once. If they come, instead, one by one and you need the temporary vector to be sorted, the complexity goes up to \sum_{i=2}^n i log(i). This is still less than n^2 I presume, but definitely more than n log n.
Is that correct?
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
编辑2：
编辑：显然，你错过了重点，所以我会尽力澄清。
首先，将 N 个元素插入数组，同时确保每次插入后数组都排序，复杂度可以为 O(N²)。您可以使用以下算法插入一个元素：
对 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²)。
EDIT 2:
EDIT: apparently, you missed the point, so I'll try to clarify.
First, inserting N elements into an array, while ensuring the array is sorted after every insert, can be done in complexity O(N²). You can use the following algorithm to insert one element:
Repeating this algorithm for N inserts thus yields \sum_i (i + log i) = O(N²).
To make it exceedingly clear : this is not insertion sort. Insertion sort would involve sorting the entire array by re-inserting all elements, while this algorithm merely inserts one element.
Second, doing this operation cannot be done faster than O(N²): inserting one element into an array of size i while keeping the array sorted is of complexity greater than O(i), because it involves moving around up to i elements. There is simply no workaround to circumvent this elementary fact: if you insert
1into[2,3,..,i], the result is[1,2,3,..,i], which means elements 2, 3 .. i had to be moved.So, the total is greater than \sum_i i = O(N²).