淺談對象數(shù)組或list排序及Collections排序原理

更新時(shí)間：2016年09月07日 11:27:53 投稿：jingxian

下面小編就為大家?guī)硪黄獪\談對象數(shù)組或list排序及Collections排序原理。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

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

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

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

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

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實(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; 
}

會調(diào)用Object的compareTo進(jìn)行比較。而默認(rèn)類似String和Integer類型都已經(jīng)覆蓋compareTo方法。所以可以自行進(jìn)行比較

2、對自定義類進(jìn)行比較

通過上面的介紹了解了Collections排序的原理，下面介紹下自定義對象的排序，先查看下Integer和String的比較原理、然后介紹如何對自定義類進(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對自定義對象進(jìn)行排序

2.3 自定義類的比較

下面代碼為對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，小于會返回-1。

若相等則按照int age的大小進(jìn)行比較。

上面的大于返回1，等于返回0，小于會返回-1也是用來binarySort比較的依據(jù)。

3、利用Collections sort的重載函數(shù)對自定義對象進(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次的移動

mergeSort是不斷進(jìn)行二分，二分到很小部分后進(jìn)行插入排序。所以會比較nlg(n)次，移動nlg(n)次。但它需要先復(fù)制一份源數(shù)據(jù)，所以會多占用一倍的空間

所以實(shí)際情況可以根據(jù)需要選擇

以上這篇淺談對象數(shù)組或list排序及Collections排序原理就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: