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

问题描述

背景

大多数关于排序的问题都是关于对现有的未排序数组进行排序。以排序顺序构造新数组是等效的问题还是不同的问题？这是一个可以解决问题的示例：

例子

我正在生成N随机数，并希望在生成它们时将它们插入到一个新数组中，并且我希望对最终数组进行排序。

可能的解决方案

插入排序

我的直觉告诉我，将每个元素放在生成的正确位置会最快。这是通过进行二分搜索以在数组中找到插入新元素的正确点来完成的。然而，这是一种插入排序，已知它在大型列表上的效率低于其他排序算法。

快速排序

快速排序通常被认为是最有效的“通用”排序算法，其中对数组的输入一无所知，并且它比大型列表上的插入排序更有效。因此，最好将随机数以未排序的顺序简单地放入数组中，然后在最后使用快速排序对它们进行排序？

其他解决方案

还有其他我没有想到的算法吗？

标签： arrayssorting

大多数关于排序的问题都是关于对现有的未排序数组进行排序。以排序顺序构造新数组是等效的问题还是不同的问题？

出于效率考虑，它归结为随机数据的相同问题。

给定随机数据，首先将随机值生成一个数组（未排序）—— 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 相同并不意味着性能相同。即使您绝对需要能够在构建数组期间的某个时间点按排序顺序获取数据，但根据需要对数组进行排序可能仍然更便宜，除非您需要在每次插入时对其进行排序！

请注意，这个答案与随机数据有关- 如果数据的大小和特征都已知，那么有可能甚至可能提出一种更有效的方法来“保持数组在构造时排序”，并遵循一些数学模式，除了随机性；但是，这种方法必然会过度拟合与其相关的特定数据集，而不是通用解决方案。