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

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

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

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

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

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

1、对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实现

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

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中用于大小比较部分为

Comparable

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

再看下String的定义

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

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

2.2 查看Comparable接口

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

Java代码

public int compareTo(T o);

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

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

2.3 自定义类的比较

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

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;

}

}

}

执行后输出为：

Xml代码：

Herry 19

Herry 20

Jack 19

James 18

James 19

Jim 19

Luccy 19

Lucy 19

可以看出只需两点即可

a、继承自Comparable

Java代码

private static class User implements Comparable

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中的一样先比较姓名，若相等再比较年龄输出

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

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

追踪Collections的

Java代码

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

到

Java代码

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

http://

到

Java代码

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

可以发现其中代码如下：

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;

}

调用Comparator的compare方法

4、以上两种排序性能的比较

binarySort需要进行nlg(n)次的比较，最坏情况下n^2次的移动

mergeSort是不断进行二分，二分到很小部分后进行插入排序。所以会比较nlg(n)次，移动nlg(n)次。但它需要先复制一份源数据，所以会多占用一倍的空间

所以实际情况可以根据需要选择

for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)

swap(dest, j, j-1);

return;

}

调用Comparator的compare方法

4、以上两种排序性能的比较

binarySort需要进行nlg(n)次的比较，最坏情况下n^2次的移动

mergeSort是不断进行二分，二分到很小部分后进行插入排序。所以会比较nlg(n)次，移动nlg(n)次。但它需要先复制一份源数据，所以会多占用一倍的空间

所以实际情况可以根据需要选择

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。