开发者社区> 范大脚脚> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

  



本文转自邴越博客园博客,原文链接:http://www.cnblogs.com/binyue/p/3569714.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
java集合框架之hashmap
hashmap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 根据需要该容器...
1968 0
Java集合框架:HashMap
Java集合框架概述   Java集合框架无论是在工作、学习、面试中都会经常涉及到,相信各位也并不陌生,其强大也不用多说,博主最近翻阅java集合框架的源码以及搜索一些相关资料整理出Java集合框架的系列。
880 0
线程 - Java 多线程编程(上)
线程 - Java 多线程编程(上)
52 0
Java多线程那些事,对Java并发编程2w余字的总结,超详细(从入门到完全掌握)
Java多线程那些事,对Java并发编程2w余字的总结,超详细(从入门到完全掌握)
70 0
java多线程中的死锁、活锁、饥饿、无锁都是什么鬼?
死锁、活锁、饥饿是关于多线程是否活跃出现的运行阻塞障碍问题,如果线程出现了这三种情况,即线程不再活跃,不能再正常地执行下去了。
61 0
五分钟带你玩转多线程(一)java多线程基础知识简介
线程概念 进程:是一个执行中的程序,如打开网易云音乐,网易云音乐就是一个进程 线程:是进程的组成,一个进程包含多个线程,是jvm最小调度单元。如网易云音乐听歌是一个线程,评价是一个线程。
47 0
Java的并发编程中的多线程问题到底是怎么回事儿?
原创: Hollis 在我之前的一篇《再有人问你Java内存模型是什么,就把这篇文章发给他。》文章中,介绍了Java内存模型,通过这篇文章,大家应该都知道了Java内存模型的概念以及作用,这篇文章中谈到,在Java并发编程中,通常会遇到三个问题,即原子性问题、一致性问题和有序性问题。
1055 0
+关注
3656
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载