淺談對(duì)象數(shù)組或list排序及Collections排序原理
常需要對(duì)list進(jìn)行排序，小到List<String>，大到對(duì)自定義的類進(jìn)行排序。不需要自行歸并或堆排序。簡(jiǎn)單實(shí)現(xiàn)一個(gè)接口即可。
本文先會(huì)介紹利用Collections對(duì)List<String>進(jìn)行排序，繼而講到Collections.sort的原理，
再講到如何對(duì)自定義類進(jìn)行排序，
最后會(huì)介紹利用Collections sort對(duì)自定義對(duì)象進(jìn)行排序的另外一種方法，并將兩種排序進(jìn)行了簡(jiǎn)單的性能比較。
1、對(duì)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實(shí)現(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實(shí)現(xiàn)為
public static void sort(Object[] array) {
// BEGIN android-changed
ComparableTimSort.sort(array);
// END android-changed
}
繼續(xù)追蹤，ComparableTimSort的sort實(shí)現(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;
}
會(huì)調(diào)用Object的compareTo進(jìn)行比較。而默認(rèn)類似String和Integer類型都已經(jīng)覆蓋compareTo方法。所以可以自行進(jìn)行比較
2、對(duì)自定義類進(jìn)行比較
通過上面的介紹了解了Collections排序的原理，下面介紹下自定義對(duì)象的排序，先查看下Integer和String的比較原理、然后介紹如何對(duì)自定義類進(jìn)行比較
2.1 我們查看Object的實(shí)現(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中只有一個(gè)方法
Java代碼
public int compareTo(T o);
也就是說實(shí)際上binarySort方法中調(diào)用的是Comparable的compareTo方法，以此可知只要繼承自Comparable，
并實(shí)現(xiàn)compareTo即可調(diào)用Collections.sort對(duì)自定義對(duì)象進(jìn)行排序
2.3 自定義類的比較
下面代碼為對(duì)User進(jìn)行排序，首先按姓名字母先后排序，若姓名相同，則按年齡由小到大排序
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
可以看出只需兩點(diǎn)即可
a、繼承自Comparable
Java代碼
private static class User implements Comparable<User>
b、實(shí)現(xiàn)compareTo方法
上面的public int compareTo(User another)為比較的主體
可以看到其中int compareName = this.name.compareTo(another.getName());表示比較姓名
若大于返回1，等于返回0，小于會(huì)返回-1。
若相等則按照int age的大小進(jìn)行比較。
上面的大于返回1，等于返回0，小于會(huì)返回-1也是用來binarySort比較的依據(jù)。
3、利用Collections sort的重載函數(shù)對(duì)自定義對(duì)象進(jìn)行排序
代碼如下，仍同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>())
為比較的主體，并且實(shí)現(xiàn)了Comparator的compare方法。下面介紹下此種方法的原理
追蹤C(jī)ollections的
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需要進(jìn)行nlg(n)次的比較，最壞情況下n^2次的移動(dòng)
mergeSort是不斷進(jìn)行二分，二分到很小部分后進(jìn)行插入排序。所以會(huì)比較nlg(n)次，移動(dòng)nlg(n)次。但它需要先復(fù)制一份源數(shù)據(jù)，所以會(huì)多占用一倍的空間
所以實(shí)際情況可以根據(jù)需要選擇
以上這篇淺談對(duì)象數(shù)組或list排序及Collections排序原理就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
在Java中,final可以別用來修飾類、修飾方法、修飾變量和修飾參數(shù)等,這里就來簡(jiǎn)單作一個(gè)Java中final關(guān)鍵字的用法總結(jié):2016-06-06
javaweb項(xiàng)目如何實(shí)現(xiàn)手機(jī)短信登錄
這篇文章主要介紹了javaweb項(xiàng)目如何實(shí)現(xiàn)手機(jī)短信登錄，手機(jī)號(hào)登錄在現(xiàn)在的項(xiàng)目中用的場(chǎng)景非常多，實(shí)現(xiàn)起來也不難，今天我們就一起來通過演示實(shí)現(xiàn)登錄過程,需要的朋友可以參考下2019-07-07
Java中Stringbuild,Date和Calendar類的用法詳解
這篇文章主要為大家詳細(xì)介紹了Java中Stringbuild、Date和Calendar類的用法，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04
Maven設(shè)置使用自定義的jar包到自己本地倉(cāng)庫(kù)
今天小編就為大家分享一篇關(guān)于Maven設(shè)置使用自定義的jar包到自己本地倉(cāng)庫(kù)的文章，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-10-10
這篇文章主要介紹了java常用工具類之DES和Base64加密解密類,需要的朋友可以參考下2014-07-07
mybatis-plus分頁(yè)查詢的實(shí)現(xiàn)實(shí)例
頁(yè)查詢是一項(xiàng)常用的數(shù)據(jù)庫(kù)查詢方法,本文主要介紹了mybatis-plus分頁(yè)查詢的實(shí)現(xiàn)實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06
基于spring?@Cacheable?注解的spel表達(dá)式解析執(zhí)行邏輯
這篇文章主要介紹了spring?@Cacheable?注解的spel表達(dá)式解析執(zhí)行邏輯，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
Java中二叉樹的先序、中序、后序遍歷以及代碼實(shí)現(xiàn)
這篇文章主要介紹了Java中二叉樹的先序、中序、后序遍歷以及代碼實(shí)現(xiàn),一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成,需要的朋友可以參考下2023-11-11
線程池運(yùn)用不當(dāng)引發(fā)的一次線上事故解決記錄分析
遇到了一個(gè)比較典型的線上問題,剛好和線程池有關(guān),另外涉及到死鎖、jstack命令的使用、JDK不同線程池的適合場(chǎng)景等知識(shí)點(diǎn),同時(shí)整個(gè)調(diào)查思路可以借鑒,特此記錄和分享一下2024-01-01
Spring boot中filter類不能注入@Autowired變量問題
這篇文章主要介紹了Spring boot中filter類不能注入@Autowired變量問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09