arrays - 持有排序数组-反向排序输入情况

Question

我从用户那里得到整数(一个接一个)，然后通过运行二进制搜索并找到插入索引，将其插入到排序的vec中正确的位置。
问题是当用户决定提供反向排序的输入(一个接一个)时，插入将很昂贵，O(n ^ 2)，因为每次插入时，vec中的所有当前元素都必须向右移动。有没有一种算法可以用更少的时间处理这个问题？
例子:

[] <- 10
[10] <- 9 // Shift x1
[9, 10] <- 8 // Shift x2
[8, 9, 10] <- 7 // Shift x3
[7, 8, 9, 10] <- 6 // Shift x4
.
.
.

Answer 1

The problem is when user decides to provide a reversed sorted input (one by one) then insertion will be expensive, O(n^2), since on each insertion, all of the current elements in the vec has to be shifted to the right.

Vec实现将一次移动所有内容(使用memcpy)，因此移动20个项目和移动1个项目并没有什么区别。如果收集的内存很大，将开始成为流量问题，但是在低arity情况下，您可以将其视为常量。

Is there an algorithm that can handle this with less time?

本质上排序的基于树的数据结构。但是Rust标准库在这方面受到一定程度的限制，并且BTreeSet仅在无论如何都要进行重复数据删除时才有效。但是不确定它会击败常规的Vec，因为它会有更多的分配。
虽然从理论上来说LinkedList提供O(1)插入，但Rust没有提供插入API，因为没有Cursor，因此您需要支付O(n-i)来寻找插入索引，然后insert()将再次向其支付遍历有问题的索引并插入新项目。