最有效的动态排序方法
可能的重复：
如何在添加时对数据进行排序添加它，不是稍后吗？
我需要即时对数据进行排序。基本上我有一个将在其中插入元素的数组。每次插入后，应对数据进行排序。实现这一目标最快的方法是什么？
Possible Duplicate:
how to sort data at the time of adding it, not later?
I need to sort data on the fly. Basically I have an array in which elements will be inserted. After each insert, the data should be sorted. What is fastest way to achieve that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
实现此目的的最快方法是删除数组并使用二叉搜索树代替 O(lg n) 排序插入。对于数组，由于平均需要移动 n/2 个元素，您将始终陷入线性时间插入的困境。
编辑：您还可以使用堆代替一个二叉搜索树；可以用数组来实现。但是，对于二进制堆，迭代需要 O(n lg n)，而在 线程 BST 它可以在 O(n) 时间内完成，并使用 O(1) 额外内存。
The fastest way to achieve this is to drop the array and use a binary search tree instead for O(lg n) sorted insertion. With an array, you'll always be stuck with linear-time insertion due to the need to shift n/2 of the elements on average.
EDIT: you can also use a heap instead of a BST; that can be implemented in terms of an array. However, iteration would take O(n lg n) for a binary heap, while in a threaded BST it can be done in O(n) time with O(1) extra memory.
如果每次插入后都对数组进行排序，那么最快的方法是使用二分搜索算法来查找应插入元素的位置，然后将所有元素从该位置开始向右向下移动一位，然后插入将元素放入您创建的间隙中。
也就是说，正如拉斯曼斯所说，如果可以的话，使用 BST 确实会更好。这样，您就可以避免每次插入元素时都必须移动所有元素。
If after each insertion the array is sorted, then the fastest way to do this would be to use a binary search algorithm to find where the element should be inserted, and shift all the elements starting at that position and going right down one, and insert the element into the gap you created.
That said, it would really be better to use a BST if you can, as larsmans said. That way you can avoid having to move potentially all the elements each time one is inserted.