连续数据流的排序算法

Question

堆排序，快速排序和合并排序中的哪些排序算法可以处理连续的数据流？我希望有一个始终排序的列表，以便新值可以立即进入正确位置的列表中。我似乎找不到始终维护排序列表并具有连续数据流的细节。

class StreamSorter<A extends Comparable <A>> { 
        // A[] sorted_list;
        // other fields and initialiser: TODO

 public void add_new_element(A x) {

 // add new element to the data received so far and create a sorted list.

  }
 }

该类将如何实现，以便每次调用add_new_element时，sorted_list包含到目前为止所有已排序的元素？

抱歉，如果这是一个愚蠢的问题，请相信我，我已经尽力了。

欢呼声

Answer 1

您可以使用TreeSet来维护排序集，并且，如果需要，可以使用TreeSet将其包装在线程安全的包装器中。

Collections.synchronizedSortedSet()

Answer 2

所以，事实是实际上无法正常工作。在任何时候，可能都会出现一个新的最低元素，并且必须一直到最开始，所以当更多元素仍在其中时，您就无法开始浏览排序列表。但是堆是sort] >所要查找的内容：可以向其中添加更多元素，并且可以逐步完成该过程，以除去到目前为止所看到的最低元素。

Answer 3

由于您说的是Collections.synchronizedSortedSet()，请使用

java.util.SortedSet<E> s = java.util.Collections.synchronizedSortedSet( new java.util.TreeSet<E>( new java.util.Comparator<E>(){
    @Override
    public int compare( final E o1, final E o2 ) {
        // Add sorting criteria.
        return 0;
    }
}));

或I want to have a list that's always sorted。 java.util.TreeSet<E>实现java.util.PriorityQueue<E>接口，因此不允许重复值。

Answer 4

如果我的理解正确，您希望将元素以即时排序的顺序存储在内存中的集合中，而不是在将所有元素都添加到集合中的逻辑点上对其进行排序。

Answer 5

我们还可以维护MaxHeap或MinHeap。我们可以在登录时间内实现。