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
.
.
.

score 0 · Accepted Answer

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

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

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

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

虽然LinkedList理论上提供了 O(1) 插入，但 Rust 不提供插入 API，因为没有 Cursor，因此您需要付费O(n-i)查找插入索引，然后insert()再次付费以遍历索引问题并插入新项目。

1 回答 1