Рекомендации по банкам для коллекций и сортировки (сортировка слиянием)

Question

Мне нужна рекомендация для хорошей реализации сортировки слиянием в Java.В принципе, я могу написать все слияния, но если у меня будет хороший кувшин от провайдера, такого как Apache или Google, это будет лучше.

Требования для сортировки слиянием:

1. Я получаю неизвестное количество отсортированных массивов.
2. Очень важно: я получаю число, которое говорит, когда нужно остановиться (позволяетскажем, в случайном инциденте написано 34 - я хочу, чтобы мой алгоритм прекратил сортировку, когда он достигнет этого числа).

Нет необходимости писать код здесь, я только ищу доступную банку /библиотека.

Answer 1

Я не знаю готового решения, но оно кажется достаточно простым для реализации с помощью очереди с приоритетами:

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 - количество найденных элементов.

Answer 2

http://www.docjar.com/html/api/java/util/Collections.java.html

 1944       @SuppressWarnings("unchecked")
 1945       public static <T extends Comparable<? super T>> void sort(List<T> list) {
 1946           Object[] array = list.toArray();
 1947           Arrays.sort(array);
 1948           int i = 0;
 1949           ListIterator<T> it = list.listIterator();
 1950           while (it.hasNext()) {
 1951               it.next();
 1952               it.set((T) array[i++]);
 1953           }
 1954       }

и вот реализации сортировки массивов:

http://www.docjar.com/html/api/java/util/Arrays.java.html

 2588       public static void sort(Object[] array) {
 2589           sort(0, array.length, array);
 2590       }


 2620       private static void sort(int start, int end, Object[] array) {
 2621           int length = end - start;
 2622           if (length <= 0) {
 2623               return;
 2624           }
 2625           if (array instanceof String[]) {
 2626               stableStringSort((String[]) array, start, end);
 2627           } else {
 2628               Object[] out = new Object[end];
 2629               System.arraycopy(array, start, out, start, length);
 2630               mergeSort(out, array, start, end);
 2631           }
 2632       }

 2666       @SuppressWarnings("unchecked")
 2667       private static void mergeSort(Object[] in, Object[] out, int start,
 2668               int end) {
 2669           int len = end - start;
 2670           // use insertion sort for small arrays
 2671           if (len <= SIMPLE_LENGTH) {
 2672               for (int i = start + 1; i < end; i++) {
 2673                   Comparable<Object> current = (Comparable<Object>) out[i];
 2674                   Object prev = out[i - 1];
 2675                   if (current.compareTo(prev) < 0) {
 2676                       int j = i;
 2677                       do {
 2678                           out[j--] = prev;
 2679                       } while (j > start
 2680                               && current.compareTo(prev = out[j - 1]) < 0);
 2681                       out[j] = current;
 2682                   }
 2683               }
 2684               return;
 2685           }
 2686           int med = (end + start) >>> 1;
 2687           mergeSort(out, in, start, med);
 2688           mergeSort(out, in, med, end);
 2689   
 2690           // merging
 2691   
 2692           // if arrays are already sorted - no merge
 2693           if (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
 2694               System.arraycopy(in, start, out, start, len);
 2695               return;
 2696           }
 2697           int r = med, i = start;
 2698   
 2699           // use merging with exponential search
 2700           do {
 2701               Comparable<Object> fromVal = (Comparable<Object>) in[start];
 2702               Comparable<Object> rVal = (Comparable<Object>) in[r];
 2703               if (fromVal.compareTo(rVal) <= 0) {
 2704                   int l_1 = find(in, rVal, -1, start + 1, med - 1);
 2705                   int toCopy = l_1 - start + 1;
 2706                   System.arraycopy(in, start, out, i, toCopy);
 2707                   i += toCopy;
 2708                   out[i++] = rVal;
 2709                   r++;
 2710                   start = l_1 + 1;
 2711               } else {
 2712                   int r_1 = find(in, fromVal, 0, r + 1, end - 1);
 2713                   int toCopy = r_1 - r + 1;
 2714                   System.arraycopy(in, r, out, i, toCopy);
 2715                   i += toCopy;
 2716                   out[i++] = fromVal;
 2717                   start++;
 2718                   r = r_1 + 1;
 2719               }
 2720           } while ((end - r) > 0 && (med - start) > 0);
 2721   
 2722           // copy rest of array
 2723           if ((end - r) <= 0) {
 2724               System.arraycopy(in, start, out, i, med - start);
 2725           } else {
 2726               System.arraycopy(in, r, out, i, end - r);
 2727           }
 2728       }

надеюсь, это поможет:)

Answer 3

Это довольно специализированный способ найти его в библиотеке общего назначения ..... Не сложно реализовать это самостоятельно.