罐推荐和排序（排序合并）

Question

我需要一个良好的执行Java中合并排序的建议。 基本上，我可以写所有的合并，但如果我必须从供应商如Apache或谷歌的好罐子还要好。

的合并排序要求：

1. 我得到一个未知数量的排序阵列。
2. 非常重要：我得到一个数字说明什么时候停止（让我们说在一个随机事件中说34） - 我希望我的算法在达到该数字时停止排序）。

不需要在这里写代码，我只是在寻找一个可用的jar /库。

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）的日志（L） ）其中L是列表的数量，K是检索到的元素的数量。

Answer 2

这是非常专业的找到它的通用库.....不难实现它自己。

Answer 3

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  } 

希望它能帮助:)