假设我有一个系统，连续不断地接收随机数字作为输入(如 0、5、2、10、6、20......)。我的目的是以最佳性能对它们进行排序。由于输入是顺序的，所以输出大小将在每次迭代后增加。我想使用插入排序或二叉搜索树，但我不确定哪种方法更适合这个问题。据我所知，插入排序的时间复杂度是O(n-n^2)，而BST插入的时间复杂度是O(log(n))。请问，有什么建议吗？
连续（非固定）输入随机数的最佳排序算法是什么？
3
- VitalyT
8
我已经编辑了我的问题，我只想将它们排序（0、2、5、6...）。 - VitalyT
2O(n-n^2) 的意思是什么？ - user1196549
@Yves Daoust 插入排序：最好情况是O(n)，最坏情况是O(n^2)。 - VitalyT
1使用跳表可以使插入操作的时间复杂度达到O(log n)。 - Thomas
随着数字的接收，系统需要何时以及如何检索先前存储在结构中的数字？如何访问排序后的数字将是一个问题，例如通过索引，或者偶尔检索整个集合。如果检索是间歇性的，那么数字可以在接收时部分排序，并且仅在使用类似于使用引用或指针的小数组进行链表的自底向上归并排序时完全排序。 - rcgldr
显示剩余3条评论
6个回答
4
如果每次添加元素时都需要排序，那么这不是一个排序问题，而是一个插入问题。任何排序算法都会过度处理。
如果您的数据必须存储在数组中，那么无法避免移动元素，解决方案的下限为Ω(N)。这可以通过直接插入（O(N)）有效实现。（二分搜索后跟插入将比较少，但不能确定您是否会注意到差异。）
如果您有更多自由，BST确实是一种更有效的解决方案。如果您需要绝对保证最坏情况下的成本（O(Log N)），则BST需要平衡（因此AVL，Red-Black...取决于您的口味）。如果您的数据足够随机，则可能不需要平衡。
如果您的数据具有特殊属性（例如小离散范围），则可以使用特定的解决方案。在给定的示例中，简单的计数直方图将实现O(1)的更新时间。
如果您的数据必须存储在数组中，那么无法避免移动元素，解决方案的下限为Ω(N)。这可以通过直接插入（O(N)）有效实现。（二分搜索后跟插入将比较少，但不能确定您是否会注意到差异。）
如果您有更多自由，BST确实是一种更有效的解决方案。如果您需要绝对保证最坏情况下的成本（O(Log N)），则BST需要平衡（因此AVL，Red-Black...取决于您的口味）。如果您的数据足够随机，则可能不需要平衡。
如果您的数据具有特殊属性（例如小离散范围），则可以使用特定的解决方案。在给定的示例中，简单的计数直方图将实现O(1)的更新时间。
- user1196549
5
我的数据只是从0到1M的随机数字范围，输出可以是数组或树，这取决于最佳性能。 - VitalyT
一直不停地...很多 - 服务器运行的时间，可能超过1百万个数字。 - VitalyT
@VitalyTarasiuk：对于如此模糊的信息，我无法做任何事情。如果你必须保留所有数据，“一直”是不可能的：机器迟早会溢出。 - user1196549
那么这个数据集太小了，无法证明使用直方图的方法，不是因为方法本身的问题，而是因为列出排序后的值会很慢。你应该回答@Thomas的问题。 - user1196549
晚来的评论：对“连续输入”进行排序似乎是一个XY问题。如果接收到了一百万个值，我怀疑每次有新值到达时都会查看整个排序后的一百万个值。原帖作者应该说明他想在什么时候/为什么要对数据进行排序。 - user1196549
3
我认为使用一些保证 O(log n) 性能的二叉搜索树（如AVL、红黑树等）是最好的选择。
利用中序遍历该树来打印当前数据。
- shapiro yaacov
1
插入排序对小型输入（小于1000）非常有效，否则由于其运行时间为O(n^2)，它的复杂度会非常快地增长。如果您不确定输入的大小将增长到多大，则使用快速排序或堆排序，它们的运行时间为O(nlogn)，比O(n^2)要快得多。
- Shadi Shaaban
7
为什么不使用一些二叉搜索树（AVL、红黑树等），这样添加操作的时间复杂度就是
O(log n) 呢？ - shapiro yaacov@Shadi Shaaban - 快速排序和堆排序使用固定大小的输入...我的输入是顺序的（不是固定的） - VitalyT
1我明白了，在这种情况下，我会采用@shapiro的建议，使用AVL、2-4或红黑树非常高效，因为它具有O(log n)的插入时间复杂度。 - Shadi Shaaban
插入排序怎么样？据我所知，它被用于像这样的“在线排序算法”，我是对的吗？或者也许是平衡树？ - VitalyT
为什么不呢？例如在“堆排序”中，最初必须构建堆，这会迭代输入大小 - 这是固定的。 - VitalyT
显示剩余2条评论
1
原始问题没有明确说明数据在接收数字时需要多频繁地检索，或者数字如何被检索（按索引，只是最小的，只是最大的，还是全部都要...）。其中一个选项是使用自底向上的链表归并排序逻辑，它使用一个包含少量（26到32个）引用或指针的数组，每个指向一个列表。Array [i] 是指向包含（2的i次方）个节点的列表的引用或指针，array [0] 指向大小为1的列表，array [1] -> 大小为2的列表，array [2] -> 大小为4的列表，数组的最后一个成员指向一个无限大小的列表。节点一个接一个地插入数组中，这对应于逐个接收数字。问题是数据存储在列表数组中，因此仅部分排序。为了获得完全排序的列表，将列表数组合并成单个列表。通常只有在所有数据存储到数组中后才执行此操作。链表自底向上归并排序的维基百科文章：
http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists
这种方法提供了快速的平均插入时间，但偶尔会出现较长时间。每个其他数字只存储在array [0]中。2的幂输入涉及多个合并步骤，第16个输入最终合并两个8个数字的列表，第1024个输入最终合并两个512个数字的列表。
如前所述，二叉搜索树（偶尔重新平衡）可能是更好的解决方案。
- rcgldr
1
有几个因素会影响您解决方案的效率：
- 查找插入点的读取数量
- 插入操作的写入数量（例如移位，重新平衡）
- 总内存/局部性（影响缓存未命中），常数(K)的大小很重要，因为它影响每个缓存级别中可以容纳多少元素。
- 分支预测未命中
请注意，这些因素更多地基于数据结构而不是算法而变化，因为每次添加元素时都会重新排序，似乎始终是插入排序的变体。
Data Structure | READS | WRITES | Memory | locality | Branches
---------------|--------|--------|------------|----------|---------
Sorted Vector |O(logN) | O(N) | O(N) | high | high (FFTFFT)
Linked List |O(N) | O(1) | O(K*N) | low | low (FFFFFFFFFFT)
Red Black Tree |O(logN) | O(K) | O(K*NlogN) | low | high (FFTFFT)
Btree 16 node |O(logN) | O(16) | O(NlogN) | medium | medium (FFTF)
* K表示与具有相同O()的其他解决方案相比，常数明显更高
最佳解决方案可能因当前架构限制而异。如果内存/缓存大小较小，则排序向量可能是最佳选择。如果分支未命中昂贵，则链表可能是最佳选择，因为除最后一个外的所有分支都将为false。
但似乎如果使用具有大量节点P的Btree，您将获得向量的局部性和内存效率，具有索引的O(logN)读取速度，并且将将写入数量限制为O(P)而不是O(N)。 我会从P开始使用16，然后使用二进制搜索来优化P，
不幸的是，真正的答案是尝试它们并针对您的用例进行基准测试。
- Glenn Teitelbaum
2
当然，它消除了移位问题。它变成了一个查找问题。也就是说，您必须按顺序遍历列表以找到插入点。这可能需要与在数组中移动项目一样多的时间。 - Jim Mischel
@JimMischel改变了我的想法，但更好地解释了权衡。 - Glenn Teitelbaum
0
这取决于你如何想要使用结果。
例如：如果你输入了很多数字，并且使用BST来存储它们，你需要超过1000步才能找到索引1000。如果你将排序后的结果存储在一个数组中，你只需要1步（返回index[1000]）。
如果你只需要最高或最低的数字，然后将其从列表中删除。之后你需要下一个最高或最低的数字，使用堆会更快。
还要记住，如果随机数字某种程度上是排序的，BST看起来像一个列表，那么插入就不是O(log n)而是O(n)了。
还有很多事情你需要考虑。所以请告诉我们你需要这个东西的目的。
- Thomas
3
同时，跳表也可以帮助你。 - Thomas
我需要一个已排序的数据结构作为输出，可以是任何形式（数组、树等），但需要在最短的处理/响应时间内完成。 - VitalyT
我认为跳表非常快速且易于实现。 - Thomas
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接