原文出處： xieyu_zy 在C、C++中有很多排序演算法，但是通常排序演算法不得不讓程式員在寫代碼的過程中陷入對底層很多指針和位置的理解，java不希望這樣，所以排序大多可以由java幫你做掉，例如，你要對一個數組排序，就通過：Collections.sort(list)那麼這個list就被排序了，
原文出處： xieyu_zy
在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介面完成中文排序）：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
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這樣一個類，描述如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
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了排序，那麼我們定義排序的類如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 |
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方法，是使用拼音排序的，然後我們來模擬一些數據驗證結果：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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("張三" , "[email protected]"));
userSet.add(new UserDO("李四" , "[email protected]"));
userSet.add(new UserDO("王五" , "[email protected]"));
for(UserDO userDO : userSet) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOList() {
List<UserDO>list = Arrays.asList(
new UserDO("張三" , "[email protected]"),
new UserDO("李四" , "[email protected]"),
new UserDO("王五" , "[email protected]")
);
Collections.sort(list , USER_COMPARATOR);
for(UserDO userDO : list) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOArray() {
UserDO []userDOArray = new UserDO[] {
new UserDO("張三" , "[email protected]"),
new UserDO("李四" , "[email protected]"),
new UserDO("王五" , "[email protected]")
};
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：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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了，就可以直接排序了，下麵是我們的測試程式：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
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("張三" , "[email protected]"));
userSet.add(new UserComparableDO("李四" , "[email protected]"));
userSet.add(new UserComparableDO("王五" , "[email protected]"));
for(UserComparableDO userDO : userSet) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOList() {
List<UserComparableDO>list = Arrays.asList(
new UserComparableDO("張三" , "[email protected]"),
new UserComparableDO("李四" , "[email protected]"),
new UserComparableDO("王五" , "[email protected]")
);
Collections.sort(list);
for(UserComparableDO userDO : list) {
System.out.println(userDO.getName());
}
}
private static void sortUserDOArray() {
UserComparableDO []userDOArray = new UserComparableDO[] {
new UserComparableDO("張三" , "[email protected]"),
new UserComparableDO("李四" , "[email protected]"),
new UserComparableDO("王五" , "[email protected]")
};
Arrays.sort(userDOArray);
for(UserComparableDO userDO : userDOArray) {
System.out.println(userDO.getName());
}
}
}
|
可以看到本次排序中沒有再使用自定義的Comparator作為參數，另外TreeSet的入口參數也沒有再傳入這些參數。
結果知道了，我們簡單看看相關的源碼來證實這個說法，我們首先來看Collections.sort方法：
源碼片段1：Collections.sort(List<T> list)
| 1 2 3 4 5 6 7 8 9 |
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)
| 1 2 3 4 5 6 7 8 9 |
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):
| 1 2 3 4 |
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)
| 1 2 3 4 5 6 7 8 |
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  更多相關文章
一周排行
 所有分類
|