固定大小数组/列表的在线排序算法

Question

维护和排序固定大小的数组(或链表？)的最佳方法是什么？为了清楚地说明情况,假设100个数据样本存储在一个缓冲区中(假设它们是为了简单而排序),那么当下一个样本进入时,最旧的一个出去,新样本必须放入缓冲区中.位置使其排序.

存储这些样本,数组或链表的最佳方法是什么？以及如何为最新的样本块排序列表？

[最初缓冲区可能初始化为0]

Answer 1

数组和链表都非常糟糕,以保持每次更新后必须保持排序的数据.要么必须在更新后求助列表(O(nlogn)),要么将新元素插入/移除/移动到排序列表中的适当位置(O(n)).

更好的想法是使用本质上排序的数据结构,并在O(log(n))中的每次更新后维护该属性.两个二叉搜索树和跳表有属性.许多语言都有一个容器,它被实现为快速排序的数据结构(例如,set在C++和TreeSetJava中).