java - 插入时排序 vs 稍后对整个数组进行排序

Question

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

1. 案例 1:将所有数据复制到数组中并排序(假设 O(nlgn))。
2. 案例 2:边将每个元素插入数组边排序。

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

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

Answer 1

将元素插入已排序的数组(又名 Insertion Sort)的问题是:虽然可以使用二进制搜索在 O(log n) 中找到插入元素的索引，但在实际插入元素时，必须移动以下所有元素，导致(平均)O(n/2) 用于插入 array[] 或 ArrayList.

当使用 LinkedList 时，元素不必移动，但在这里，您也不能进行二分查找:找到要插入的索引大约是 O( n/4)(根据 this overview )，以及另一个用于实际插入元素的 O(n/4)，添加到 O(n/2)，与 ArrayList 相同。 (您可以创建自定义 Skip List 以提供更快的查找和同时插入，但 AFAIK Java 不提供 something like this。)

如果数字是唯一的，您可以考虑将它们插入到 TreeSet 中，然后在最后调用 toArray。插入每个数字将是 O(log n)，总共 O(n log n)，还有一个额外的 O(n)每次你按排序顺序得到数字。 (根据您的评论，它们不是唯一的，但也许这对其他人有帮助。)您仍然可以使用 TreeMap 使用此方法的变体，将元素映射到它们的数量，但这会更复杂实现。

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

“排序插入”会给你(平均)O(log n + n/2) = O(n/2) 来插入每个 n 个数，总计 O(n²/2)，同时始终保持排序数组。最后的排序是 O(1) 用于插入 n 个数字中的每一个加上 O(n log n) 在最后(或者当你需要在两者之间排序的列表时)，导致 O(n + k n log n) = O(k n log n) 排序 k > 0 次。 (如果我们求解 k，我们会发现只要 k < n/2 log n，最后的排序就会更快。)