arrays - 构造一个新的、已排序的数组的最有效方法是什么？

Question

背景
大多数关于排序的问题都是关于对现有的未排序数组进行排序。按排序顺序构造新数组是等效问题还是不同的问题？这是一个可以解决问题的示例:
例子
我正在生成 N随机数并希望在生成它们时将它们插入到一个新数组中，并且我希望对最终数组进行排序。
可能的解决方案
插入排序
我的直觉告诉我，将每个元素在生成时放在正确的位置会是最快的。这是通过进行二分搜索来找到数组中的正确点以插入新元素来实现的。然而，这是一种插入排序，众所周知，它在大型列表上的效率低于其他排序算法。
快速排序
快速排序通常被认为是最有效的“通用”排序算法，其中对数组的输入一无所知，并且它比大列表上的插入排序更有效。因此，最好将随机数以未排序的顺序放入数组中，然后在最后使用快速排序对它们进行排序吗？
其他解决方案
有没有我没有想到的另一种算法？

Answer 1

Most questions around sorting talk about sorting an existing unsorted array. Is constructing a new array in a sorted order an equivalent problem or a different one? 

由于效率考虑，它归结为随机数据的相同问题。
给定随机数据，首先将随机值生成到数组(未排序)中实际上更有效 - O(n) 时间复杂度 - 然后使用您最喜欢的 O(n log n) 排序算法对其进行排序，使整个操作 O( 2n log n) 时间复杂度，并且取决于所使用的排序算法，在 O(1) 和 O(n) 空间复杂度之间。
对于随机数据，无法通过“保持数组按其构造排序”来击败该方法，因为任何方法都需要精确地 O(n) 代/插入值，并且至少需要 O(n log n) 次比较/交换/类次 - 无论使用哪种方法，都来自对原始问题的评论中提到的众多方法。请注意，根据对我的原始答案的非常有用的评论，原始问题中建议的二进制插入排序变体可能会降低到 O(n^2) 时间复杂度，使其成为仅先生成值数组的劣质解决方案，然后然后排序。
使用平衡树只匹配生成数组然后对其进行排序的时间复杂度 - 但会损失空间复杂度，因为与数组相比，树有一些开销，以跟踪子节点等。另外值得注意的是，树是堆分配，访问任何子节点都需要指针解引用操作——所以即使Big-O时间复杂度相当于先生成一个数据数组然后对其进行排序，树解决方案的实际性能会更差，因为没有数据局部性，并且有额外的指针取消引用成本。对平衡树的另一个考虑是，插入到像 AVL 这样的东西中的成本相当高——也就是说，AVL 的 O(n log n) 插入中的 n 与就地排序数组中的 n 的成本不同，由于树节点的必要旋转以实现平衡。仅仅因为 Big-O 相同并不意味着性能相同。即使您绝对需要能够在构建数组的某个时间点按排序顺序获取数据，根据需要对数组进行排序仍然可能更便宜，除非您需要在每次插入时对其进行排序!
请注意，此答案与随机数据有关 - 如果数据的大小和特征都已知，则有可能，甚至有可能提出一种更有效的方法来“保持数组在构造时排序”，并遵循一些数学模式，随机性除外；然而，这种方法对于它所涉及的特定数据集必然会过度拟合，而不是通用解决方案。