连续数据流的排序算法

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时，排序后的列表都包含迄今为止所有已排序的元素？

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

干杯

- Oscar

---

您能澄清“连续数据流”吗？如果它是持续的，那么您无法对其进行排序，因为排序算法适用于有限列表。您可以按块对其进行排序，但我认为这不是您要问的内容。或者，如果您正在接收输入流并保留迄今为止看到的所有内容的已排序列表，则插入排序是合适的。 - lurker

与其将排序算法与无序数据结构相结合，为什么不寻找一种可以保持元素排序的数据结构呢？例如TreeBag/TreeMultiset或类似的数据结构。您还可以编写自己的List子类，覆盖add()/insert()方法，并在每次调用后重新对自身进行排序。 - Craig Otis

请查看PriorityQueue。您可以将对象放入其中，每当您取出它们时，它们总是按排序顺序出现。 - Misha

顺便提一下，在Java中方法名中没有下划线（通常情况下）。惯例是使用驼峰命名法，例如addNewElement，更好的选择是只用add。 - mike

Answer 1

您可以使用TreeSet来维护一个有序集合，并且如果需要的话，可以使用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;
    }
}));

- MT0

Answer 2

所以，问题在于它实际上不能正常工作。随时可能会出现新的最低元素，并且必须直接进入开头，因此在仍有更多元素进入时无法开始遍历已排序的列表。但是堆 就是 你要找的东西：你可以向其中添加更多元素，并且可以通过它逐步进行操作，取出目前为止看到的最低元素。

- Louis Wasserman

Answer 3

如果我理解正确 - 您希望在内存集合中按顺序存储元素，并且不在所有元素添加到集合时在逻辑点上进行排序。

如果这是正确的理解 - 您正在寻找SortedSet的实现 - 其中一个示例是TreeSet。

请注意，您的元素需要可比较。当然，限制在于内存利用率 - 考虑到您正在流式传输，很可能具有相对较大的数据负载。

快速而简单的示例：

package com.mytrial;

import java.util.Set;
import java.util.TreeSet;


public class StreamSorterExample {

    private static class MyDataFromStream implements Comparable<MyDataFromStream> {
        int someWeight;

        public MyDataFromStream(int someWeight) {
            this.someWeight = someWeight;
        }

        @Override
        public String toString() {
            return Integer.toString(someWeight);
        }

        @Override
        public int compareTo(MyDataFromStream that) {
            return this.someWeight - that.someWeight;
        }
    };

    public static void main(String[] args) {
        Set<MyDataFromStream> streamedData = new TreeSet<MyDataFromStream>();

        streamedData.add(new MyDataFromStream(10));
        streamedData.add(new MyDataFromStream(3));
        streamedData.add(new MyDataFromStream(5));

        System.out.println(streamedData);

        streamedData.add(new MyDataFromStream(111));
        streamedData.add(new MyDataFromStream(-1));

        System.out.println(streamedData);
    };
};

输出

[3, 5, 10]
[-1, 3, 5, 10, 111]

- Y123

Answer 4

由于您说过，我想要一个始终排序的列表，因此使用java.util.TreeSet<E>或java.util.PriorityQueue<E>。 TreeSet实现了Set接口，因此不允许重复值。

请注意，插入的元素必须具有自然排序，即实现Comparable<T>或者您必须提供Comparator<T>。

有关排序数据结构的更多信息，请查看stackoverflow上的以下问题。

- mike