algorithm - 连续(不固定)输入随机数的最佳排序算法是什么？

Question

假设我有一个系统，一直接收一个一个连续的随机数作为输入 (0,5,2,10,6,20......) ,

我的目的是以最佳性能对它们进行排序。

因此每次迭代后输出大小都会增加并且输入是顺序的。

我想使用插入排序或 BST，但我不确定对于这个问题哪个更好，因为我知道插入排序是 O(n-n^2) 而 BST 插入是 O(log(n))

请问有什么建议吗？

Answer 1

如果每次添加元素都需要排序，这不是排序问题而是插入问题。任何排序算法都会矫枉过正。

如果你的数据必须存储在一个数组中，你不能不移动元素，解决方案是 Ω(N)。这可以通过直接插入 (O(N)) 有效地实现。 (先进行二分搜索再插入会进行较少的比较，但不确定您是否会注意到差异。)

如果你有更多的自由，BST 确实是一个更有效的解决方案。如果您需要对最坏情况成本 (O(Log N)) 的绝对保证，则 BST 需要平衡(因此 AVL、红黑……根据您的喜好)。如果您的数据足够随机，则可能没有必要。

如果您的数据具有特殊属性(例如小的离散范围)，可以使用临时解决方案。在给定的示例中，一个简单的计数直方图将实现 O(1) 更新时间。