维护和排序固定大小数组(或链表？)的最佳方法是什么？为了使情况更清楚，假设 100 个数据样本存储在缓冲区中(为简单起见，假设它们已排序)，然后当下一个样本进入时，最旧的样本将消失，并且新样本必须按顺序放入缓冲区位置使其排序。
存储这些样本、数组或链表的最佳方式是什么？以及如何对最新样本 block 的列表进行排序？
[最初缓冲区可能被初始化为0]
最佳答案
数组和链表都很难保持每次更新后必须保持排序的数据。要么必须在更新后对列表求助 (O(nlogn))，要么将新元素插入/删除/移动到已排序列表 (O(n)) 中的适当位置。
更好的想法是使用一种固有排序的数据结构，并在 O(log(n)) 的每次更新后维护该属性。两者 binary search trees和 skip lists拥有那个属性(property)。许多语言都有一个实现为快速排序数据结构的容器(例如，C++ 中的 set 和 Java 中的 TreeSet)。
关于algorithm - 固定大小数组/列表的在线排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6709981/