594
人物
Java對象排序、中文排序、SortedSet排序使用和源碼講解
在C、C++中有很多排序算法，但是通常排序算法不得不讓程序員在寫代碼的過程中陷入對底層很多指針和位置的理解，java不希望這樣，所以排序大多可以由java幫你做掉，例如，你要對一個數組排序，就通過：Collections.sort(list)那麼這個list就被排序了，排序最終調用的是Arrays.sort方法來完成的，所以數組自然是用Arrays.sort了，而SortedSet裏麵內部也有排序功能也是類似的方式的來實現的，隻是內部調用了相關的方法來完成而已；SortedSet隻是一個接口，實現類有很多，本文以TreeSet實現類作為例子。
而排序必然就存在對比大小，那麼傳遞的信息，java是通過什麼來對比大小的呢？compareTo這個來對比的，而內部對比過程中，需要將數據轉換為Comparable來對比，所以你的對象就需要implementsComparable，並實現內部的方法compareTo，隻要你的compareTo實現是你所想要的，那麼排序必然是正確的，那麼是否還有其他的方法，有的，排序的時候，允許你傳入一個對比類，因為這樣也可以減少一些空指針出現的可能性，傳入的類需要實現：Comparator接口，實現其方法：compare類，雖然接口中還定義了equals方法基本不用管它，因為Object就已經實現了，並且內部排序中並沒有用到equals方法來做排序。
下麵開始使用實例分別來做中文排序、對象排序，並分別使用對象實現Comparable接口，以及單獨定義排序對象實現Comparator接口來完成排序：
實例1（通過實現Comparator接口完成中文排序）：
import java.text.Collator;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ChineseSortCompare {
@SuppressWarnings("rawtypes")
private final static Comparator CHINA_COMPARE = Collator.getInstance(java.util.Locale.CHINA);
public static void main(String []args) {
sortArray();
sortList();
System.out.println("李四".compareTo("張三"));//前者大於後者，則為正數，否則為負數，相等為0
}
@SuppressWarnings("unchecked")
private static void sortList() {
List<String>list = Arrays.asList("張三", "李四", "王五");
Collections.sort(list , CHINA_COMPARE);
for(String str : list) {
System.out.println(str);
}
}
@SuppressWarnings("unchecked")
private static void sortArray() {
String[] arr = {"張三", "李四", "王五"};
Arrays.sort(arr, CHINA_COMPARE);
for(String str : arr) {
System.out.println(str);
}
}
}
可以看到輸出的結果都是一樣的，當然String本身有compare方法，而且其本身也是實現了Comparable接口的，所以你如果不放入CHINA_COMPARE來進行處理的話，將會默認按照String自己的compareTo來做排序，排序的結果自然不是你想要的，當然英文應該是你想要的。
實例2（通過外部定義Comparator來完成對象排序）：
這裏首先要構造一個對象的類，為了簡單，我們就用兩屬性，定義一個UserDO這樣一個類，描述如下：
public class UserDO {
protected String name;
protected String email;
public UserDO() {}
public UserDO(String name , String email) {
this.name = name;
this.email = email;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getEmail() {
return email;
}
public void setEmail(String email) {
this.email = email;
}
}
定義了兩個屬性為name和email，此時我們想要按照name了排序，那麼我們定義排序的類如下：
import java.text.Collator;
import java.util.Comparator;
public class UserDOComparator implements Comparator<UserDO> {
Collator cmp = Collator.getInstance(java.util.Locale.CHINA);
@Override
public int compare(UserDO userDO1, UserDO userDO2) {
return cmp.compare(userDO1.getName(), userDO2.getName());
}
}
此時可以看出我們實現了compare方法，是使用拚音排序的，然後我們來模擬一些數據驗證結果：
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortUserListTest {
private final static UserDOComparator USER_COMPARATOR = new UserDOComparator();
public static void main(String []args) {
sortUserDOArray();
sortUserDOList();
sortUserBySortedSet();
}
private static void sortUserBySortedSet() {
SortedSet<UserDO>userSet = new TreeSet<UserDO>(USER_COMPARATOR);
userSet.add(new UserDO("張三" , "aaazhangsan@ddd.com"));
userSet.add(new UserDO("李四" , "ddlisi@dsfds.com"));
userSet.add(new UserDO("王五" , "ddwangwu@fsadfads.com"));
for(UserDO userDO : userSet) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOList() {
List<UserDO>list = Arrays.asList(
new UserDO("張三" , "aaazhangsan@ddd.com"),
new UserDO("李四" , "ddlisi@dsfds.com"),
new UserDO("王五" , "ddwangwu@fsadfads.com")
);
Collections.sort(list , USER_COMPARATOR);
for(UserDO userDO : list) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOArray() {
UserDO []userDOArray = new UserDO[] {
new UserDO("張三" , "aaazhangsan@ddd.com"),
new UserDO("李四" , "ddlisi@dsfds.com"),
new UserDO("王五" , "ddwangwu@fsadfads.com")
};
Arrays.sort(userDOArray , USER_COMPARATOR);
for(UserDO userDO : userDOArray) {
System.out.println(userDO.getName());
}
}
}
根據這些輸入，你可以看到它的輸出和實際想要的按照名稱的拚音排序是一致的，那麼有人會問，如果我按照兩個字段排序，先按照一個字段排序，再按照另一個字段排序該怎麼辦，其次如果是倒敘應該是如何操作，其實倒敘來講隻需要在compare方法中將原有的輸出改成相反數就可以了，compare得到的結果為正數、負數、或0，若為正數，代表第一個數據比第二個大，而負數相反，為0的時候代表相等；而多字段排序也是如此，通過第一層排序後得到結果，看是否是0，如果是0，那麼就再按照第二個字段排序即可，否則就直接返回第一層返回的結果，兩者混合應用以及多層排序自然就實現了。
實例3（將上麵的UserDO使用一個叫UserComparableDO在類的基礎上進行排序）
首先將UserDO重新編寫為UserComparableDO：
import java.text.Collator;
import java.util.Comparator;
public class UserComparableDO extends UserDO implements Comparable<UserDO> {
public UserComparableDO() {}
public UserComparableDO(String name , String email) {
this.name = name;
this.email = email;
}
@SuppressWarnings("rawtypes")
private final static Comparator CHINA_COMPARE = Collator.getInstance(java.util.Locale.CHINA);
@SuppressWarnings("unchecked")
@Override
public int compareTo(UserDO userDO) {
return CHINA_COMPARE.compare(this.getName(), userDO.getName());
}
}
當然這段代碼裏麵直接在裏麵定義一個Comparator是不正確的，一般這個東西是被抽象到係統某些公共的Commons組件裏麵的，其次，如果原本沒有UserDO類，相應的屬性寫一次即可，我這裏原本有UserDO所有直接集成，減少很多代碼。
此時就不需要自己再去寫一個Comparator了，就可以直接排序了，下麵是我們的測試程序：
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortUserListByComparable {
public static void main(String []args) {
sortUserBySortedSet();
sortUserDOList();
sortUserDOArray();
}
private static void sortUserBySortedSet() {
SortedSet<UserComparableDO>userSet = new TreeSet<UserComparableDO>();
userSet.add(new UserComparableDO("張三" , "aaazhangsan@ddd.com"));
userSet.add(new UserComparableDO("李四" , "ddlisi@dsfds.com"));
userSet.add(new UserComparableDO("王五" , "ddwangwu@fsadfads.com"));
for(UserComparableDO userDO : userSet) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOList() {
List<UserComparableDO>list = Arrays.asList(
new UserComparableDO("張三" , "aaazhangsan@ddd.com"),
new UserComparableDO("李四" , "ddlisi@dsfds.com"),
new UserComparableDO("王五" , "ddwangwu@fsadfads.com")
);
Collections.sort(list);
for(UserComparableDO userDO : list) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOArray() {
UserComparableDO []userDOArray = new UserComparableDO[] {
new UserComparableDO("張三" , "aaazhangsan@ddd.com"),
new UserComparableDO("李四" , "ddlisi@dsfds.com"),
new UserComparableDO("王五" , "ddwangwu@fsadfads.com")
};
Arrays.sort(userDOArray);
for(UserComparableDO userDO : userDOArray) {
System.out.println(userDO.getName());
}
}
}
可以看到本次排序中沒有再使用自定義的Comparator作為參數，另外TreeSet的入口參數也沒有再傳入這些參數。
結果知道了，我們簡單看看相關的源碼來證實這個說法，我們首先來看Collections.sort方法：
源碼片段1：Collections.sort(List<T> list)
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]);
}
}
此時直接調用了Arrays.sort(a)來排序後，將數組的數據寫回到list，另外根據方法的定義，泛型T要求傳入的類必須是Comparable類的子類或實現類，所以要調用Collections.sort(list)這個方法，傳入的list中包含的每行數據必須是implements Comparable這個接口的，否則編譯時就會報錯。
再看重載方法，傳入自定義的Comparator
源碼片段2：Collections.sort(List<T> list, Comparator<? super T> c)
public static <T> void sort(List<T> list, Comparator<? super T> c) {
Object[] a = list.toArray();
Arrays.sort(a, (Comparator)c);
ListIterator i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set(a[j]);
}
}
也是和第一個方法類似，就是調用了Arrays.sort相應的重載方法，看來都是在Arrays裏麵是實現的，那麼就進一步向下看：
源碼片段3：Arrays.sort(T[]t):
public static void sort(Object[] a) {
Object[] aux = (Object[])a.clone();
mergeSort(aux, a, 0, a.length, 0);
}
看來代碼片段交給了mergeSort來處理，而對數組做了一次克隆，作為排序的基礎數據，而原來的數組作為排序的目標，mergeSort的代碼片段應該是核心部分，我們先放在這裏，先看下sort的另一個重載方法，另外需要注意，這裏並沒有像Collections.sort(List<T>list)那樣在編譯時檢查類型，也就是在使用這個方法的時候，數組裏麵的每行並沒有implements Comparable也會不會出錯，隻是在運行時會報錯而已，在下麵的源碼中會有說明。
源碼片段4 : Arrays.sort(T[]t, Comparator<? super T> c)
public static <T> void sort(T[] a, Comparator<? super T> c) {
T[] aux = (T[])a.clone();
if (c==null)
mergeSort(aux, a, 0, a.length, 0);
else
mergeSort(aux, a, 0, a.length, 0, c);
}
看來mergeSort也進行了重載，也就是當傳入了自定義的Comparator和不傳入自定義的Comparator是調用不同的方法來實現的，然後我們來看下兩個方法的實現。
源碼片段5：mergeSort(Object[]src , Object[]dst , int low , int high , int off)
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
/**
* Swaps x[a] with x[b].
*/
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}
仔細閱讀代碼可以發現排序是分段遞歸回調的方式來排序（注意中間的low和high兩個參數的變化），每次如果分段的大小大於INSERTIONSORT_THRESHOLD（定義為7）的時候，則再分段，前一段和後一段，然後分開的兩段再調用遞推，遞推後再回歸排序，若發現中間分隔的位置兩個數據是有序，則認為兩段是完全有序的，若不是，那麼再將兩段做一次排序，此時排序就很好排序了，因為兩個塊是排序排好的，所以不需要兩次循環，隻需要循環掃描下去，兩個數組按照順序向下走，分別對比出最小值寫入數組，較大者暫時不寫入數組與另一個數組的下一個值進行對比，最後一截數據（源碼中是通過越界來判定的）寫入到尾巴當中：
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
這段對兩個有序數組的排序是很經典的寫法，主要是if語句的濃縮，不然代碼會寫得很長。
注意：這裏的代碼排序中使用了強製類型轉換為Comparable來調用內部的comareTo方法，所以如果你的類沒有implements Comparable那麼在Collections.sort(List<T>list)時編譯時會報錯上麵已經說到，在調用Arrays.sort(Object []t)時，編譯時並不會報錯，但是運行時會報錯為：java.lang.ClassCastExceptionXXXDO cannot be cast to java.lang.Comparable
排序部分我們再看看其重載的mergeSort方法，就是傳入了自定義的Comparator的方法
源碼片段6： mergeSort(Object[]src,Object[]dst,int low,int high,intoff,Comparator c)
private static void mergeSort(Object[] src,
Object[] dest,
int low, int high, int off,
Comparator c) {
int length = high - low;
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;
}
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off, c);
mergeSort(dest, src, mid, high, -off, c);
if (c.compare(src[mid-1], src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
可以發現算法和上一個方法完全一樣，唯一的區別就是排序時使用的compare變成了傳入的comparator了，其餘的沒有任何區別。
大概清楚了，此時發現java提供的排序還是比較高效的，大多數情況下你不需要自己去寫排序算法，最後我們再看看TreeSet中的在add的時候如何實現排序的，也是分別傳入了comparator和沒有傳入，我們跟著源碼裏麵，可以看到傳入了comparator將這個屬性設置給了TreeSet裏麵定義的一個TreeeMap，而TreeMap中的一個屬性設置了這個Comparator：
源碼片段7：TreeSet以及TreeMap設置Comparator的構造方法
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<E,Object>(comparator));
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
當然沒有傳入這個Comparator的時候自然沒有設置到TreeMap中了，那麼我們來看看TreeMap的add方法：
源碼片段8：TreeSet#add(E e)
public boolean add(E e) {
return m.put(e,PRESENT)==null;
}
這個m是什麼呢？其實通過源碼片段7就可以看出，m是開始實例化的一個TreeMap，那麼我們就需要看TreeMap的put方法
代碼片段9：TreeMap#put(K key , V value)
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
這裏判定了是否存在Comparator進行不同方式來寫入不同的位置，並沒有重載方法，所以實現上也不一定有什麼絕對非要如何做，隻需要保證代碼可讀性很好就好，一切為它服務，否則那些過多的設計是屬於過度設計，當然並不是說代碼設計不重要，但是這些需要適可而止；另外TreeSet裏麵對於其他的方法也會做排序處理，我們這裏僅僅是用add方法來做一個例子而已。
相信你對java的排序有了一些了解，也許本文說了一堆廢話，因為本文不是在說排序算法，我們隻是告訴你java是如何排序的，你在大部分情況下無需自己寫排序算法來完成排序導致一些不必要的bug，而且效率未必有java本身提供的排序算法高效。
最後更新：2017-04-04 07:03:54