对象数组或list排序及Collections排序原理

常需要对list进行排序，小到List<String>，大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。

本文先会介绍利用Collections对List<String>进行排序，继而讲到Collections.sort的原理，

再讲到如何对自定义类进行排序，

最后会介绍利用Collections sort对自定义对象进行排序的另外一种方法，并将两种排序进行了简单的性能比较。

下文中提到的如何追踪Collections等类的ava源代码，可以参考：http://trinea.iteye.com/blog/1351233

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实现

@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实现为

public static void sort(Object[] array) {  
    // BEGIN android-changed  
    ComparableTimSort.sort(array);  
    // END android-changed  
}

继续追踪，ComparableTimSort的sort实现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中用于大小比较部分为

Java代码

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

会调用Object的compareTo进行比较。而默认类似String和Integer类型都已经覆盖compareTo方法。所以可以自行进行比较

2、对自定义类进行比较

通过上面的介绍了解了Collections排序的原理，下面介绍下自定义对象的排序，先查看下Integer和String的比较原理、然后介绍如何对自定义类进行比较

2.1 我们查看Object的实现发现其中并没有compareTo方法，

再看下Integer定义

public final class Integer extends Number implements Comparable<Integer>

再看下String的定义

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

我们可以发现他们都继承自Comparable

2.2 查看Comparable接口

可以发现Comparable中只有一个方法

public int compareTo(T o);

也就是说实际上binarySort方法中调用的是Comparable的compareTo方法，以此可知只要继承自Comparable，

并实现compareTo即可调用Collections.sort对自定义对象进行排序

2.3 自定义类的比较

下面代码为对User进行排序，首先按姓名字母先后排序，若姓名相同，则按年龄由小到大排序

执行后输出为：

Xml代码

Herry 19
Herry 20
Jack 19
James 18
James 19
Jim 19
Luccy 19
Lucy 19

可以看出只需两点即可

a、继承自Comparable

private static class User implements Comparable<User>

b、实现compareTo方法

上面的public int compareTo(User another)为比较的主体

可以看到其中int compareName = this.name.compareTo(another.getName());表示比较姓名

若大于返回1，等于返回0，小于会返回-1。

若相等则按照int age的大小进行比较。

上面的大于返回1，等于返回0，小于会返回-1也是用来binarySort比较的依据。

3、利用Collections sort的重载函数对自定义对象进行排序

代码如下，仍同2中的一样先比较姓名，若相等再比较年龄输出

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

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

可以看出其中

Collections.sort(userList, new Comparator<User>())

为比较的主体，并且实现了Comparator的compare方法。下面介绍下此种方法的原理

追踪Collections的

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

public static <T> void sort(T[] a, Comparator<? super T> c)

private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c)

可以发现其中代码如下：

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

调用Comparator的compare方法

来源于：http://trinea.iteye.com/blog/1248517