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

时间:2021-09-23 08:19:05

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

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

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

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

1、对List<String>排序及Collections.sort的原理

代码如下

?
1
2
3
4
5
6
7
8
9
10
11
12
13
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实现

?
1
2
3
4
5
6
7
8
9
10
11
@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实现为

?
1
2
3
4
5
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中用于大小比较部分为

?
1
2
3
4
5
6
7
8
9
10
11
12
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定义

?
1
public final class Integer extends Number implements Comparable<Integer>

再看下String的定义

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

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

2.2 查看Comparable接口

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

Java代码

?
1
public int compareTo(T o);

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

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

2.3 自定义类的比较

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

Java代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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; 
    
  
}

执行后输出为:

Xml代码:

?
1
2
3
4
5
6
7
8
Herry    19
Herry    20
Jack    19
James    18
James    19
Jim   19
Luccy    19
Lucy    19

可以看出只需两点即可

a、继承自Comparable

Java代码

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

Java代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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代码

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

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

追踪Collections的

Java代码

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

Java代码

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

Java代码

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

可以发现其中代码如下:

Java代码

?
1
2
3
4
5
6
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方法

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

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

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

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

以上这篇浅谈对象数组或list排序及Collections排序原理就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持服务器之家。