背景

这年头想必没几个人没写过排序吧。。。而在jdk也默认提供了许多和排序相关的封装。

我们最常使用的想必就是

/**  * Sorts the specified list into ascending order, according to the  * {@linkplain Comparable natural ordering} of its elements.  * All elements in the list must implement the {@link Comparable}  * interface.  Furthermore, all elements in the list must be  * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)}  * must not throw a {@code ClassCastException} for any elements  * {@code e1} and {@code e2} in the list).  *  * <p>This sort is guaranteed to be <i>stable</i>:  equal elements will  * not be reordered as a result of the sort.  *  * <p>The specified list must be modifiable, but need not be resizable.  *  * <p>Implementation note: This implementation is a stable, adaptive,  * iterative mergesort that requires far fewer than n lg(n) comparisons  * when the input array is partially sorted, while offering the  * performance of a traditional mergesort when the input array is  * randomly ordered.  If the input array is nearly sorted, the  * implementation requires approximately n comparisons.  Temporary  * storage requirements vary from a small constant for nearly sorted  * input arrays to n/2 object references for randomly ordered input  * arrays.  *  * <p>The implementation takes equal advantage of ascending and  * descending order in its input array, and can take advantage of  * ascending and descending order in different parts of the same  * input array.  It is well-suited to merging two or more sorted arrays:  * simply concatenate the arrays and sort the resulting array.  *  * <p>The implementation was adapted from Tim Peters's list sort for Python  * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">  * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic  * Sorting and Information Theoretic Complexity", in Proceedings of the  * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,  * January 1993.  *  * <p>This implementation dumps the specified list into an array, sorts  * the array, and iterates over the list resetting each element  * from the corresponding position in the array.  This avoids the  * n<sup>2</sup> log(n) performance that would result from attempting  * to sort a linked list in place.  *  * @param  list the list to be sorted.  * @throws ClassCastException if the list contains elements that are not  *         <i>mutually comparable</i> (for example, strings and integers).  * @throws UnsupportedOperationException if the specified list's  *         list-iterator does not support the {@code set} operation.  * @throws IllegalArgumentException (optional) if the implementation  *         detects that the natural ordering of the list elements is  *         found to violate the {@link Comparable} contract  */ public static <T extends Comparable<? super T>> void sort(List<T> list) {     Object[] a = list.toArray();     Arrays.sort(a);     ListIterator<T> i = list.listIterator();     for (int j=0; j<a.length; j++) {         i.next();         i.set((T)a[j]);     } }

问题

虽然通常来说我们使用jdk的默认已经足够 但是始终会有一些莫名其妙的问题要来。

比如使用sort接口要求必须实现 Comparable 前几篇文章我们也聊过关于 Comparable这个接口在官方说明中

/**  * Compares this object with the specified object for order.  Returns a  * negative integer, zero, or a positive integer as this object is less  * than, equal to, or greater than the specified object.  *  * <p>The implementor must ensure <tt>sgn(x.compareTo(y)) ==  * -sgn(y.compareTo(x))</tt> for all <tt>x</tt> and <tt>y</tt>.  (This  * implies that <tt>x.compareTo(y)</tt> must throw an exception iff  * <tt>y.compareTo(x)</tt> throws an exception.)  *  * <p>The implementor must also ensure that the relation is transitive:  * <tt>(x.compareTo(y)&gt;0 &amp;&amp; y.compareTo(z)&gt;0)</tt> implies  * <tt>x.compareTo(z)&gt;0</tt>.  *  * <p>Finally, the implementor must ensure that <tt>x.compareTo(y)==0</tt>  * implies that <tt>sgn(x.compareTo(z)) == sgn(y.compareTo(z))</tt>, for  * all <tt>z</tt>.  *  * <p>It is strongly recommended, but <i>not</i> strictly required that  * <tt>(x.compareTo(y)==0) == (x.equals(y))</tt>.  Generally speaking, any  * class that implements the <tt>Comparable</tt> interface and violates  * this condition should clearly indicate this fact.  The recommended  * language is "Note: this class has a natural ordering that is  * inconsistent with equals."  *  * <p>In the foregoing description, the notation  * <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical  * <i>signum</i> function, which is defined to return one of <tt>-1</tt>,  * <tt>0</tt>, or <tt>1</tt> according to whether the value of  * <i>expression</i> is negative, zero or positive.  *  * @param   o the object to be compared.  * @return  a negative integer, zero, or a positive integer as this object  *          is less than, equal to, or greater than the specified object.  *  * @throws NullPointerException if the specified object is null  * @throws ClassCastException if the specified object's type prevents it  *         from being compared to this object.  */ public int compareTo(T o);

在对应为空抛出空指针。不过这个逻辑被大家的实现覆盖的比较多了。但是我们也不能保证所有的比较器都会特殊处理null。

比如一个典型的例子

@Test(expected = NullPointerException.class) public void testDefaultSortString(){     List<String> list = Lists.newArrayList("1","2","2222","我是中国人",null,null,"222"," ","","aaa");     System.out.println("Input List: ");     System.out.println(list);     Collections.sort(list);     System.out.println("sort List: ");     System.out.println(list); }

这个在string为空比较就会抛出空指针。比较头疼

/**  * Compares two strings lexicographically.  * The comparison is based on the Unicode value of each character in  * the strings. The character sequence represented by this  * <code>String</code> object is compared lexicographically to the  * character sequence represented by the argument string. The result is  * a negative integer if this <code>String</code> object  * lexicographically precedes the argument string. The result is a  * positive integer if this <code>String</code> object lexicographically  * follows the argument string. The result is zero if the strings  * are equal; <code>compareTo</code> returns <code>0</code> exactly when  * the {@link #equals(Object)} method would return <code>true</code>.  * <p>  * This is the definition of lexicographic ordering. If two strings are  * different, then either they have different characters at some index  * that is a valid index for both strings, or their lengths are different,  * or both. If they have different characters at one or more index  * positions, let <i>k</i> be the smallest such index; then the string  * whose character at position <i>k</i> has the smaller value, as  * determined by using the &lt; operator, lexicographically precedes the  * other string. In this case, <code>compareTo</code> returns the  * difference of the two character values at position <code>k</code> in  * the two string -- that is, the value:  * <blockquote><pre>  * this.charAt(k)-anotherString.charAt(k)  * </pre></blockquote>  * If there is no index position at which they differ, then the shorter  * string lexicographically precedes the longer string. In this case,  * <code>compareTo</code> returns the difference of the lengths of the  * strings -- that is, the value:  * <blockquote><pre>  * this.length()-anotherString.length()  * </pre></blockquote>  *  * @param   anotherString   the <code>String</code> to be compared.  * @return  the value <code>0</code> if the argument string is equal to  *          this string; a value less than <code>0</code> if this string  *          is lexicographically less than the string argument; and a  *          value greater than <code>0</code> if this string is  *          lexicographically greater than the string argument.  */ public int compareTo(String anotherString) {     int len1 = value.length;     int len2 = anotherString.value.length;     int lim = Math.min(len1, len2);     char v1[] = value;     char v2[] = anotherString.value;       int k = 0;     while (k < lim) {         char c1 = v1[k];         char c2 = v2[k];         if (c1 != c2) {             return c1 - c2;         }         k++;     }     return len1 - len2; }

因此关于一些特殊值的处理需要注意。

Ordering

Guava在这一块很有经验。

通常使用Ordering进行一些比较。

实现了java的Comparator接口 通常我们使用一些静态方法进行Ordering的创建

通常我们使用如下一些方法

典型的关于String的比较我们如下

@Test public void testGuavaSortString(){     List<String> list = Lists.newArrayList("1","2","2222","我是中国人",null,null,"222"," ","","aaa");     System.out.println("Input List: ");     System.out.println(list);     Collections.sort(list,Ordering.natural().nullsLast());     System.out.println("sort List: ");     System.out.println(list);     Collections.sort(list,Ordering.natural().nullsLast().<String>reverse());     System.out.println("sort List: ");     System.out.println(list); }

输出如下

Input List: [1, 2, 2222, 我是中国人, null, null, 222,  , , aaa] sort List: [,  , 1, 2, 222, 2222, aaa, 我是中国人, null, null] sort List: [null, null, 我是中国人, aaa, 2222, 222, 2, 1,  , ]

这样就简单了 我们很容易做出各种比较器的组合！！！相当强大！！！

链式调用

虽然Ordering很强 但是也很容易造成理解上的困难

比如这样

@Test public void testGuavaSortNullString(){     List<String> list = Lists.newArrayList("1","2","2222","我是中国人",null,null,"222"," ","","aaa");     System.out.println("Input List: ");     System.out.println(list);     Collections.sort(list,Ordering.natural().nullsLast().<String>nullsFirst());     System.out.println("sort List: ");     System.out.println(list); }

究竟null排在前面还在后面呢？？？

[null, null, ,  , 1, 2, 222, 2222, aaa, 我是中国人]

这是因为每次都是将前一个Ordering包装起来 所以必须从后向前阅读 这是自然先做了null放在前面的操作！！！

除了nature之外usingToString也比较常用。

彩蛋

onResultOf

该方法非常神奇的提供了转化功能 可以返回一个sortkey

比如我们使用User对应进行比较时使用对应的PK进行比较

@Test public void testAppUser(){    List<TAppUser> appUserList=Lists.newArrayList(null,null,new TAppUser());    Collections.sort(appUserList,Ordering.<Integer>natural().onResultOf(new Function<TAppUser, Integer>() {        @Nullable        @Override        public Integer apply( TAppUser input) {            return input.getId();        }    }).<TAppUser>nullsFirst());     System.out.println("sort List: ");     System.out.println(appUserList); }

很明显 对于我们利用既定的比较器相当方便！！！