collection的sort方法用的什么排序

技术分享 · 2022年7月2日 · 258 次浏览

通过Collection的sort方法对List进行排序，有两种方法实现：

1. List中的对象应继承Comparable接口，并实现其compareTo方法。

   //需要比较的对象类PersonH

[java]
view plain
copy

  1. public class PersonH implements Comparable  
  2. {  
  3.   
  4.       
  5.     private int level;  
  6.       
  7.     public Integer getLevel()  
  8.     {  
  9.         return level;  
  10.     }  
  11.     public void setLevel(Integer level1)  
  12.     {  
  13.         this.level = level1;  
  14.     }  
  15.     Override  
  16.     public int compareTo(PersonH o)  
  17.     {  
  18.         // TODO Auto-generated method stub  
  19.       return this.getLevel().compareTo(o.getLevel());         
  20.     }     
  21. }  

  //Main类测试

[java]
view plain
copy

  1. public class Main  
  2. {  
  3.   
  4.     /** 
  5.      * @param args 
  6.      */  
  7.     public static void main(String[] args)  
  8.     {  
  9.         // TODO Auto-generated method stub  
  10.         PersonH person  = new PersonH();  
  11.         person.setLevel(6);  
  12.         PersonH person2 = new PersonH();  
  13.         person2.setLevel(8);  
  14.         PersonH person3 = new PersonH();  
  15.         person3.setLevel(3);  
  16.         ArrayList personList = new ArrayList();  
  17.           
  18.         personList.add(person);  
  19.         personList.add(person2);  
  20.         personList.add(person3);  
  21.           
  22.         Collections.sort(personList);//排序  
  23.         for(PersonH personH : personList) //输出排序后结果  
  24.         {  
  25.             System.out.println(personH.getLevel());  
  26.         }  
  27.     }  
  28.   
  29. }  

这中方式相当与类personH具备了指定的基本排序策略，因它实现了compareTo方法。


2. 根据Collection.sort重载之，来实现。

//PersonH类

[java]
view plain
copy

  1. public class PersonH   
  2. {  
  3.   
  4.       
  5.     private int level;  
  6.       
  7.     public Integer getLevel()  
  8.     {  
  9.         return level;  
  10.     }  
  11.     public void setLevel(Integer level1)  
  12.     {  
  13.         this.level = level1;  
  14.     }     
  15. }  


//Main类

[java]
view plain
copy

  1. public class Main  
  2. {  
  3.   
  4.     /** 
  5.      * @param args 
  6.      */  
  7.     public static void main(String[] args)  
  8.     {  
  9.         // TODO Auto-generated method stub  
  10.         PersonH person  = new PersonH();  
  11.         person.setLevel(6);  
  12.         PersonH person2 = new PersonH();  
  13.         person2.setLevel(8);  
  14.         PersonH person3 = new PersonH();  
  15.         person3.setLevel(3);  
  16.         ArrayList personList = new ArrayList();  
  17.           
  18.         personList.add(person);  
  19.         personList.add(person2);  
  20.         personList.add(person3);  
  21.         //这里可以更加灵活地指定比较策略，第一种实现方法是在要比较对象的类中就固定了比较策略。  
  22.         Collections.sort(personList,new Comparator()  
  23.         {  
  24.             public int compare(PersonH p1,PersonH p2)  
  25.             {  
  26.                 return p1.getLevel().compareTo(p2.getLevel());
  27.             }  
  28.         });  
  29.         for(PersonH personH : personList)  
  30.         {  
  31.             System.out.println(personH.getLevel());  
  32.         }  
  33.     }  
  34.   
  35. }  

下面看一下该方法是如何进行排序的：

对于第一种：

[java]
view plain
copy

  1. public static <T extends Comparable<? super T>> void sort(List list) {  
  2.     Object[] a = list.toArray();  
  3.     Arrays.sort(a);  
  4.     ListIterator i = list.listIterator();  
  5.     for (int j=0; j<a.length; j++) {  
  6.         i.next();  
  7.         i.set((T)a[j]);  
  8.     }  
  9.     }  
[java]
view plain
copy

  1. public static void sort(Object[] a) {  
  2.        Object[] aux = (Object[])a.clone();  
  3.        mergeSort(aux, a, 0, a.length, 0); 
  4.    }  

可以看出是直接调用归并排序进行的。


对于第二种：

[java]
view plain
copy

  1. public static  void sort(List list, Comparator<? super T> c) {  
  2.     Object[] a = list.toArray();  
  3.     Arrays.sort(a, (Comparator)c);  
  4.     ListIterator i = list.listIterator();  
  5.     for (int j=0; j<a.length; j++) {  
  6.         i.next();  
  7.         i.set(a[j]);  
  8.     }  
  9.     }  
[java]
view plain
copy

  1. public static  void sort(T[] a, Comparator<? super T> c) {  
  2.     T[] aux = (T[])a.clone();  
  3.         if (c==null)  
  4.             mergeSort(aux, a, 0, a.length, 0);  
  5.         else  
  6.             mergeSort(aux, a, 0, a.length, 0, c);  
  7.     }  

总之，两种方式都是通过mergeSort实现的。

首先看是否指定排序策略，如果没有，则和第一种走一样的逻辑；否则进行指定比较策略的归并排序。

mergeSort函数的源代码可以参考java.util.Arrays类。