我需要一个建议,以便在Java中很好地实现合并排序。
基本上,我可以编写所有合并,但是如果我从诸如Apache或Google之类的提供商那里得到一个好的jar,那就更好了。
合并排序的要求:
我得到未知数量的排序数组。
非常重要:我得到一个表示何时停止的数字(假设随机事件为34-我希望我的算法在达到该数字时停止排序)。
无需在这里编写代码,我只是在寻找可用的jar /库。
最佳答案
我不知道现成的解决方案,但是看起来很简单,可以借助优先级队列来实现:
import static java.util.Arrays.asList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
public class MergingIterator<T> implements Iterator<T> {
public static class InputIter<T> {
final Iterator<T> source;
T data;
public InputIter(Iterable<T> list) {
source = list.iterator();
read();
}
public void read() {
if (source.hasNext()) {
data = source.next();
} else {
data = null;
}
}
}
final PriorityQueue<InputIter<T>> queue;
public MergingIterator(final Comparator<? super T> cmp, Iterable<T>... lists) {
queue = new PriorityQueue<InputIter<T>>(lists.length, new Comparator<InputIter<T>>() {
@Override
public int compare(InputIter<T> o1, InputIter<T> o2) {
return cmp.compare(o1.data, o2.data);
}
});
for (Iterable<T> list : lists) {
InputIter<T> ii = new InputIter<T>(list);
if (ii.data != null) {
queue.add(ii);
}
}
}
@Override
public boolean hasNext() {
return !queue.isEmpty();
}
@Override
public T next() {
InputIter<T> ii = queue.poll();
T next = ii.data;
ii.read();
if (ii.data != null) {
queue.add(ii);
}
return next;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
测试代码:
Comparator<Integer> cmp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
};
List<Integer> empty = asList();
Iterator<Integer> iter = new MergingIterator<Integer> (
cmp,
asList(1, 2, 4, 5, 7, 8),
asList(3),
asList(6, 9),
asList(0),
empty
);
while (iter.hasNext()) {
System.out.println(iter.next());
}
空间复杂度为O(L),时间复杂度为O((L + K)log(L)),其中L是列表数,K是检索到的元素数。