常需要對list進行排序，小到List<String>，大到對自定義的類進行排序。不需要自行歸并或堆排序。簡單實現(xiàn)一個接口即可。
本文先會介紹利用Collections對List<String>進行排序，繼而講到Collections.sort的原理，
再講到如何對自定義類進行排序，
最后會介紹利用Collections sort對自定義對象進行排序的另外一種方法，并將兩種排序進行了簡單的性能比較。
1、對List<String>排序及Collections.sort的原理
代碼如下
List<String> stringList = new ArrayList<String>(); stringList.add("nice"); stringList.add("delicious"); stringList.add("able"); stringList.add("moon"); stringList.add("try"); stringList.add("friend"); Collections.sort(stringList); for (String str : stringList) { System.out.println(str); } 其中Collections為java.util.Collections。
查看Collections中的sort實現(xiàn)
@SuppressWarnings("unchecked") public static <T extends Comparable<? super T>> void sort(List<T> list) { Object[] array = list.toArray(); Arrays.sort(array); int i = 0; ListIterator<T> it = list.listIterator(); while (it.hasNext()) { it.next(); it.set((T) array[i++]); } } 從中可以看出排序主體為Arrays.sort(array);Arrays的sort實現(xiàn)為
public static void sort(Object[] array) { // BEGIN android-changed ComparableTimSort.sort(array); // END android-changed } 繼續(xù)追蹤，ComparableTimSort的sort實現(xiàn)ComparableTimSort.sort
static void sort(Object[] a)到static void sort(Object[] a, int lo, int hi)到private static void binarySort(Object[] a, int lo, int hi, int start)。在binarySort中用于大小比較部分為
Comparable<Object> pivot = (Comparable) a[start]; int left = lo; int right = start; assert left <= right; while (left < right) { int mid = (left + right) >>> 1; if (pivot.compareTo(a[mid]) < 0) right = mid; else left = mid + 1; } 會調(diào)用Object的compareTo進行比較。而默認類似String和Integer類型都已經(jīng)覆蓋compareTo方法。所以可以自行進行比較
2、對自定義類進行比較
通過上面的介紹了解了Collections排序的原理，下面介紹下自定義對象的排序，先查看下Integer和String的比較原理、然后介紹如何對自定義類進行比較
2.1 我們查看Object的實現(xiàn)發(fā)現(xiàn)其中并沒有compareTo方法，
再看下Integer定義
public final class Integer extends Number implements Comparable<Integer>
再看下String的定義
public final class String implements java.io.Serializable, Comparable<String>, CharSequence
我們可以發(fā)現(xiàn)他們都繼承自Comparable
2.2 查看Comparable接口
可以發(fā)現(xiàn)Comparable中只有一個方法
Java代碼
public int compareTo(T o);
也就是說實際上binarySort方法中調(diào)用的是Comparable的compareTo方法，以此可知只要繼承自Comparable，
并實現(xiàn)compareTo即可調(diào)用Collections.sort對自定義對象進行排序
2.3 自定義類的比較
下面代碼為對User進行排序，首先按姓名字母先后排序，若姓名相同，則按年齡由小到大排序
Java代碼
public class MainTest { public static void main(String[] args) { List<User> userList = new ArrayList<User>(); userList.add(new User("Lucy", 19)); userList.add(new User("Jack", 19)); userList.add(new User("Jim", 19)); userList.add(new User("James", 19)); userList.add(new User("Herry", 19)); userList.add(new User("Luccy", 19)); userList.add(new User("James", 18)); userList.add(new User("Herry", 20)); Collections.sort(userList); for (User user : userList) { System.out.println(user.getName() + "/t/t" + user.getAge()); } } private static class User implements Comparable<User> { private String name; private int age; public User(String name, int age){ this.name = name; this.age = age; } @Override public int compareTo(User another) { int compareName = this.name.compareTo(another.getName()); if (compareName == 0) { return (this.age == another.getAge() ? 0 : (this.age > another.getAge() ? 1 : -1)); } return compareName; } public String getName() { return name; } public int getAge() { return age; } } } 執(zhí)行后輸出為：
Xml代碼：
Herry 19 Herry 20 Jack 19 James 18 James 19 Jim 19 Luccy 19 Lucy 19
可以看出只需兩點即可
a、繼承自Comparable
Java代碼
private static class User implements Comparable<User>
b、實現(xiàn)compareTo方法
上面的public int compareTo(User another)為比較的主體
可以看到其中int compareName = this.name.compareTo(another.getName());表示比較姓名
若大于返回1，等于返回0，小于會返回-1。
若相等則按照int age的大小進行比較。
上面的大于返回1，等于返回0，小于會返回-1也是用來binarySort比較的依據(jù)。
3、利用Collections sort的重載函數(shù)對自定義對象進行排序
代碼如下，仍同2中的一樣先比較姓名，若相等再比較年齡輸出
Java代碼
public class MainTest { public static void main(String[] args) { List<User> userList = new ArrayList<User>(); userList.add(new User("Lucy", 19)); userList.add(new User("Jack", 19)); userList.add(new User("Jim", 19)); userList.add(new User("James", 19)); userList.add(new User("Herry", 19)); userList.add(new User("Luccy", 19)); userList.add(new User("James", 18)); userList.add(new User("Herry", 20)); Collections.sort(userList, new Comparator<User>() { public int compare(User user1, User user2) { int compareName = user1.getName().compareTo(user2.getName()); if (compareName == 0) { return (user1.getAge() == user2.getAge() ? 0 : (user1.getAge() > user2.getAge() ? 1 : -1)); } return compareName; } }); for (User user : userList) { System.out.println(user.getName() + "/t/t" + user.getAge()); } } private static class User { private String name; private int age; public User(String name, int age){ this.name = name; this.age = age; } public String getName() { return name; } public int getAge() { return age; } } } 可以看出其中
Java代碼
Collections.sort(userList, new Comparator<User>())
為比較的主體，并且實現(xiàn)了Comparator的compare方法。下面介紹下此種方法的原理
追蹤Collections的
Java代碼
public static <T> void sort(List<T> list, Comparator<? super T> c)
到
Java代碼
public static <T> void sort(T[] a, Comparator<? super T> c)
到
Java代碼
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c)
可以發(fā)現(xiàn)其中代碼如下：
Java代碼
if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; } 調(diào)用Comparator的compare方法
4、以上兩種排序性能的比較
binarySort需要進行nlg(n)次的比較，最壞情況下n^2次的移動
mergeSort是不斷進行二分，二分到很小部分后進行插入排序。所以會比較nlg(n)次，移動nlg(n)次。但它需要先復(fù)制一份源數(shù)據(jù)，所以會多占用一倍的空間
所以實際情況可以根據(jù)需要選擇
以上這篇淺談對象數(shù)組或list排序及Collections排序原理就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持武林網(wǎng)。
新聞熱點
疑難解答
圖片精選
