插入时排序 vs 稍后排序整个数组

Question

假设我有一个包含整数 (<10^6) 的文件。我需要使用这些整数创建一个排序数组。考虑以下情况

1. 案例 1：将所有数据复制到一个数组中并排序（假设 O(nlgn)）。
2. 情况 2：在将每个元素插入数组时进行排序。

哪个更安全，为什么？哪个更快，为什么？如果整数的数量进一步增加 (>10^9) ，那意味着什么？

我尝试了这两种情况，并且“排序后”在速度方面产生了更好的结果。我明白为什么，但是有没有更好的方法来处理情况 2（当前检查输入元素与数组中的每个元素以找到它的合适位置）。

Answer 1

将元素插入到已经排序的数组（又名插入排序）中的问题是：虽然可以使用二分搜索在 O(log n) 中找到插入元素的索引，但在实际插入元素时，以下所有操作元素必须被移动，导致插入到or中的（平均） O(n/2)。array[]ArrayList

\n\n

使用 a 时LinkedList，元素不必移动，但在这里，您也不能进行二分搜索：查找要插入的索引大约是O(n/4)（根据此概述），而另一个O(n/4)实际插入元素，添加到O(n/2)，与 相同ArrayList。（您可以创建一个自定义的跳过列表，以提供更快的查找和同时插入，但 AFAIK Java 不提供类似的功能。）

\n\n

如果号码是唯一的，您可以考虑将它们插入到 a 中TreeSet，然后toArray在最后调用。插入每个数字的时间复杂度为O(log n)，总共为O(n log n) ，每次按排序顺序获取数字时都会增加O(n) 。（根据您的评论，它们不是唯一的，但这可能对其他人有帮助。）您仍然可以使用此方法的变体，使用 a TreeMap，将元素映射到其计数，但这实现起来会更复杂。

\n\n

因此，将数字收集在array[]orArrayList或LinkedList，然后在最后排序似乎更好——当然，前提是您不需要在每个步骤中都需要数组的排序版本。

\n\n

“排序插入”将为您提供（平均）O(log n + n/2) = O(n/2)来插入n个数字中的每一个，总共O(n\xc2\xb2/2)，同时始终保持有序数组。最后的排序是O(1)，用于插入 n 个数字中的每一个，加上最后的O(n log n)（或者当您需要中间的排序列表时），结果是O(n + kn log n) = O (kn log n)用于排序k > 0次。（如果我们求解k，我们会发现只要k < n / 2 log n ，最后的排序就会更快。）

\n