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

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

问题是，当用户决定提供反向排序输入（一个接一个）时，插入将是昂贵的，O(n^2)，因为每次插入时，vec 中的所有当前元素都必须转移到对吧。

Vec

实现将一次移动所有内容（使用memcpy），因此移动20个项目和移动1个并没有真正产生任何区别。如果集合是巨大，内存流量将开始成为一个问题，但在低数量时，您可以将其视为常量。

有没有一种算法可以用更少的时间处理这个问题？

本质上排序的基于树的数据结构。但 Rust 标准库在这方面有些限制，并且 BTreeSet 仅在您进行重复数据删除时才起作用。但不确定它会击败常规 Vec，因为它会有更多的分配数量。

虽然

LinkedList

理论上提供 O(1) 插入，但 Rust 不提供插入 API，因为没有 Cursor，所以你需要支付

O(n-i)

来查找插入索引，然后

insert()

将再次支付费用以遍历到有问题的索引并插入新项目。

Answer 2

使用

VecDeque

，它是一个“用可增长的环形缓冲区实现的双端队列”，这意味着推到前面和推到后面一样有效。推到中间仍然会移动元素以腾出空间。

它支持随机索引、

binary_search

、

insert

，以及常规

Vec

所做的几乎所有操作，但它不会解引用到切片，因为其基础数据可能不连续。