Java集合框架实现自定义排序

简介:

Java集合框架针对不同的数据结构提供了多种排序的方法,
虽然很多时候我们可以自己实现排序,比如数组等,但是灵活的使用JDK提供的排序方法,可以提高开发效率,而且通常JDK的实现要比自己造的轮子性能更优化。

1.使用Arrays对数组进行排序

Java API对Arrays类的说明是:此类包含用来操作数组(比如排序和搜索)的各种方法。

(1)使用Arrays排序

Arrays使用非常简单,直接调用sort()即可:

1
2
3
4
5
6
7
8
9
10
11
int [] arr =  new  int [] { 5 , 8 ,- 2 , 0 , 10 };
         Arrays.sort(arr);
         for ( int  i= 0 ;i<arr.length;i++){
             System.out.print(arr[i]+ "," );
         }
                 
         char [] charArr =  new  char [] { 'b' , 'a' , 'c' , 'd' , 'D' };
         Arrays.sort(charArr);
         for ( int  i= 0 ;i<arr.length;i++){
             System.out.print(charArr[i]+ "," );
         }

如果需要降序排序, 升序排序后逆序即可:

1
Collections.reverse(Arrays.asList(arr)); 

(2)Arrays.sort()的实现

查看源码会发现,Arrays.sort()有许多重载的方法,如sort(int[] a)、sort(long[] a) 、sort(char[] a)等,

1
2
3
public  static  void  sort( int [] a) {
        DualPivotQuicksort.sort(a);
    }

但最终都是调用了DualPivotQuicksort.sort(a)的方法,

这是一个改进的快速排序,采用多路快速排序法,比单路快速排序法有更好的性能,
并且根据数组长度不同会最终选择不同的排序实现,

看一下这个方法的实现,这里不作展开:  

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
public  static  void  sort( char [] a) {
         sort(a,  0 , a.length -  1 );
     }
     
  public  static  void  sort( char [] a,  int  left,  int  right) {
         // Use counting sort on large arrays
         if  (right - left > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
             int [] count =  new  int [NUM_CHAR_VALUES];
 
             for  ( int  i = left -  1 ; ++i <= right;
                 count[a[i]]++
             );
             for  ( int  i = NUM_CHAR_VALUES, k = right +  1 ; k > left; ) {
                 while  (count[--i] ==  0 );
                 char  value = ( char ) i;
                 int  s = count[i];
 
                 do  {
                     a[--k] = value;
                 while  (--s >  0 );
             }
         else  // Use Dual-Pivot Quicksort on small arrays
             doSort(a, left, right);
         }
     }

  

1
2
3
4
5
6
private  static  void  doSort( char [] a,  int  left,  int  right) {
         // Use Quicksort on small arrays
         if  (right - left < QUICKSORT_THRESHOLD) {
             sort(a, left, right,  true );
             return ;
         }  


2.使用Comparator或Comparable进行自定义排序

集合框架中,Collections工具类支持两种排序方法:

Collections.sort(List<T> list);
Collections.sort(List<T> list, Comparator<? super T> c)

如果待排序的列表中是数字或者字符,可以直接使用Collections.sort(list);

当需要排序的集合或数组不是单纯的数字型时,需要自己定义排序规则,实现一个Comparator比较器。

下面了解一下Comparable和Comparator的应用。

Comparable 是排序接口,一个类实现了Comparable接口,就意味着该类支持排序。 

Comparable 的定义如下:

1
2
3
public  interface  Comparable<T> {
     public  int  compareTo(T o);
}

接口中通过x.compareTo(y) 来比较x和y的大小。若返回负数,意味着x比y小;返回零,意味着x等于y;返回正数,意味着x大于y

当然这里的大于等于小于的意义是要根据我们的排序规则来理解的

Comparator是比较器接口,如果需要控制某个类的次序,而该类本身没有实现Comparable接口,也就是不支持排序,那么可以建立一个类需要实现Comparator接口即可,在这个接口里制定具体的排序规则,
Comparator接口的定义如下:

1
2
3
4
public  interface  Comparator<T> {
     int  compare(T o1, T o2);
     boolean  equals(Object obj);
} 

一个比较器类要实现Comparator接口一定要实现compareTo(T o1, T o2) 函数,如果没有必要,可以不去重写equals() 函数。
因为在Object类中已经实现了equals(Object obj)函数方法。

int compare(T o1, T o2)  和上面的x.compareTo(y)类似,定义排序规则后返回正数,零和负数分别代表大于,等于和小于。

 

3.如何对HashMap的key或者value排序

HashMap作为kay-value结构,本身是无序的,排序比较灵活,一般会通过一个list进行保存。

下面的代码针对HashMap的key和value排序,提供几种实现的思路:

(1)转换为key数组,按照key排序

1
2
3
4
5
Object[] key_arr = hashmap.keySet().toArray();    
Arrays.sort(key_arr);    
for   (Object key : key_arr) {    
     Object value = hashmap.get(key);    
}  

(2)对HashMap的value进行排序

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
49
50
51
52
53
/**
  * 针对HashMap的value进行排序
  * @author Bingyue
  */
public  class  HashMapSort {
 
     public  static  void  main(String[] args) {
         HashMap<String, Integer> map =  new  HashMap<String, Integer>(){{
             put( "tom" 18 );
             put( "jack" 25 );
             put( "susan" 20 );
             put( "rose" 38 );
         }};
          
         ValueComparator cmptor =  new  ValueComparator(map); 
         /**
          * 转换为有序的TreeMap进行输出
          */
         TreeMap<String, Integer> sorted_map =  new  TreeMap<String, Integer>(cmptor);
         sorted_map.putAll(map);
          
         for (String sortedkey : sorted_map.keySet()){
             System.out.println(sortedkey+map.get(sortedkey));
         }
         /**
          * 转换为有序的list进行排序
          */
         List<String> keys =  new  ArrayList<String>(map.keySet());
         Collections.sort(keys, cmptor);
         for (String key : keys) {
              System.out.println(key+map.get(key));
         }
     }
     static  class  ValueComparator  implements  Comparator<String> {
         HashMap<String, Integer> base_map;
         public  ValueComparator(HashMap<String, Integer> base_map) {
             this .base_map = base_map;
         }
         public  int  compare(String arg0, String arg1) {
             if  (!base_map.containsKey(arg0) || !base_map.containsKey(arg1)) {
                 return  0 ;
             }
             //按照value从小到大排序
             if  (base_map.get(arg0) < base_map.get(arg1)) {
                 return  - 1 ;
             else  if  (base_map.get(arg0) == base_map.get(arg1)) {
                 return  0 ;
             else  {
                 return  1 ;
             }
         }
     }
}

输出:

tom18     
susan20   
jack25    
rose38   
tom18   
susan20  
jack25    
rose38    

4.通过Comparator自定义实体排序

如果你的List包装的是基本类型或者String,只要Collections.sort(list)即可,
但是如果list中保存的是实体bean等,就需要自己定义排序规则。

Java可以对ArrayList中的对象按照该对象某属性排序,下面的操作实现对Person实体列表的排序:

(1)定义Person实体类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public  class  Person{
      String name;
      int  age;
  public  Person(String name, int  age){
      this .name = name;
      this .age = age; 
  }
 
  public  int  getAge() {
      return  age;
  }
  public  void  setAge( int  age) {
      this .age = age;
  }
  public  String getName() {
      return  name;
  }
  public  void  setName(String name) {
      this .name = name;
  }
} 

(2)实现Comparator接口,编写排序规则

1
2
3
4
5
6
7
8
9
10
public  class  Mycomparator  implements  Comparator{<br> // 实现Comparator接口,也就是定义排序规则
     public  int  compare(Object o1,Object o2) {
         Person p1=(Person)o1;
         Person p2=(Person)o2;
        if (p1.age<p2.age)
            return  1 ;
        else
            return  0 ;
        }
} 


(3)测试排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public  class  ListSort {
      public  static  void  main(String[] args){
          ArrayList list =  new  ArrayList();
          list.add( new  Person( "lcl" , 28 ));
          list.add( new  Person( "fx" , 23 ));
          list.add( new  Person( "wqx" , 29 ));
          Comparator comp =  new  Mycomparator();
          Collections.sort(list,comp);
          for ( int  i =  0 ;i<list.size();i++){
              Person p = (Person)list.get(i);
              System.out.println(p.getName());
          }
    
      }
  
}

  


目录
相关文章
剑指 Offer 45. 把数组排成最小的数 Java自定义排序
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
|
Java
Java - Map 自定义排序 Lambda 之 Comparator
Java - Map 自定义排序 Lambda 之 Comparator
1236 0
|
6月前
|
存储 安全 Java
java集合框架及其特点(List、Set、Queue、Map)
java集合框架及其特点(List、Set、Queue、Map)
|
存储 缓存 安全
Java集合框架(Map篇)
在这个示例代码中,首先定义了一个数组和一个集合,并使用Arrays.asList()方法将数组转换成集合。接着对数组和集合分别进行排序,使用binarySearch()方法查找元素位置,使用copyOf()和copy()方法复制数组和集合,最后输出结果。可以看到,Arrays和Collections提供的方法可以方便地对数组和集合进行操作,节省开发者的时间和精力。
|
6月前
|
Java 程序员
Java集合框架:List、Set、Map类型及泛型详解
Java集合框架:List、Set、Map类型及泛型详解
100 0
|
3月前
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set
|
存储 Java
java集合框架------Map接口与实现类
java集合框架------Map接口与实现类
|
6月前
|
存储 安全 算法
【深入探究Java集合框架】从List到Map的完整指南
【深入探究Java集合框架】从List到Map的完整指南
|
6月前
|
存储 算法 Java
【Java 集合框架API接口】Collection,List,Set,Map,Queue,Deque
【Java 集合框架API接口】Collection,List,Set,Map,Queue,Deque
|
存储 算法 Java
java集合框架Map之HashMap底层原理解析
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) , 当HashMap中的table数组(桶)的长度 >= 阈值的时候就会自动触发扩容机制
68 0