我需要计算一个1D直方图，必须动态维护和经常查找。我的一个想法是用数据保持一个有序的数组（因为这样我就可以确定o（1）中的百分位数，这就足够快速地找到一个直方图，其中包含的非均匀点在每个点内都是完全相同的）。
那么，有没有一种方法可以在保持有序的同时将一个数插入到有序数组中小于o（n）？
我想答案是众所周知的，但我对算法不太了解（物理学家很少做数值计算）。
最佳答案
在一般情况下，可以使用更灵活的树状数据结构。这将允许在O（log）时间中访问、插入和删除，并且也相对容易从库中获得（Ex:c++的STL映射）。
（或哈希映射…）
带二元搜索的有序数组与树做相同的事情，但更为严格它可能更快的访问和内存使用，但你将支付时，必须插入或删除东西在中间（O（n）成本）。
但是，注意一个有序的数组可能对你来说足够了：如果你的数据点经常是相同的，你可以保存一对成对的键{键，计数}，按键排序，能够快速地添加现有项的另一个实例（但是仍然需要做更多的工作来添加新的项）。
关于algorithm - 更新有序数字数组的最快方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6876143/