我需要一个建议,以便在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是检索到的元素数。

10-07 19:28
查看更多