常需要對(duì)list進(jìn)行排序，小到List，大到對(duì)自定義的類進(jìn)行排序。不需要自行歸并或堆排序。簡(jiǎn)單實(shí)現(xiàn)一個(gè)接口即可。

本文先會(huì)介紹利用Collections對(duì)List進(jìn)行排序，繼而講到Collections.sort的原理，

再講到如何對(duì)自定義類進(jìn)行排序，

最后會(huì)介紹利用Collections sort對(duì)自定義對(duì)象進(jìn)行排序的另外一種方法，并將兩種排序進(jìn)行了簡(jiǎn)單的性能比較。

1、對(duì)List排序及Collections.sort的原理

代碼如下

List stringList = new ArrayList();

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 > void sort(List list) {

Object[] array = list.toArray();

Arrays.sort(array);

int i = 0;

ListIterator 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 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)行比較

通過(guò)上面的介紹了解了Collections排序的原理，下面介紹下自定義對(duì)象的排序，先查看下Integer和String的比較原理、然后介紹如何對(duì)自定義類進(jìn)行比較

2.1 我們查看Object的實(shí)現(xiàn)發(fā)現(xiàn)其中并沒(méi)有compareTo方法，

再看下Integer定義

public final class Integer extends Number implements Comparable

再看下String的定義

public final class String implements java.io.Serializable, Comparable, CharSequence

我們可以發(fā)現(xiàn)他們都繼承自Comparable

2.2 查看Comparable接口

可以發(fā)現(xiàn)Comparable中只有一個(gè)方法

Java代碼

public int compareTo(T o);

也就是說(shuō)實(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 userList = new ArrayList();

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 {

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

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也是用來(lái)binarySort比較的依據(jù)。

3、利用Collectionssort的重載函數(shù)對(duì)自定義對(duì)象進(jìn)行排序

代碼如下，仍同2中的一樣先比較姓名，若相等再比較年齡輸出

Java代碼

public class MainTest {

public static void main(String[] args) {

List userList = new ArrayList();

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() {

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())

為比較的主體，并且實(shí)現(xiàn)了Comparator的compare方法。下面介紹下此種方法的原理

追蹤C(jī)ollections的

Java代碼

public static void sort(List list, Comparator super T> c)

到

Java代碼

public static 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

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è)參考，也希望大家多多支持腳本之家。

總結(jié)

以上是生活随笔為你收集整理的java list数组排序_浅谈对象数组或list排序及Collections排序原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。