常需要对list进行排序,小到List<String>,大到对自定义的类进行排序。不需要自行归并或堆排序。简单实现一个接口即可。
本文先会介绍利用Collections对List<String>进行排序,继而讲到Collections.sort的原理,
再讲到如何对自定义类进行排序,
最后会介绍利用Collections sort对自定义对象进行排序的另外一种方法,并将两种排序进行了简单的性能比较。
下文中提到的如何追踪Collections等类的ava源代码,可以参考:http://trinea.iteye.com/blog/1351233
1、对List<String>排序及Collections.sort的原理
代码如下
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实现
@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实现为
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<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定义
public final class Integer extends Number implements Comparable<Integer>
再看下String的定义
public final class String implements java.io.Serializable, Comparable<String>, CharSequence
我们可以发现他们都继承自Comparable
2.2 查看Comparable接口
可以发现Comparable中只有一个方法
public int compareTo(T o);
也就是说实际上binarySort方法中调用的是Comparable的compareTo方法,以此可知只要继承自Comparable,
并实现compareTo即可调用Collections.sort对自定义对象进行排序
2.3 自定义类的比较
下面代码为对User进行排序,首先按姓名字母先后排序,若姓名相同,则按年龄由小到大排序
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; } } }
执行后输出为:
Herry 19 Herry 20 Jack 19 James 18 James 19 Jim 19 Luccy 19 Lucy 19
可以看出只需两点即可
a、继承自Comparable
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中的一样先比较姓名,若相等再比较年龄输出
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; } } }
可以看出其中
Collections.sort(userList, new Comparator<User>())
为比较的主体,并且实现了Comparator的compare方法。下面介绍下此种方法的原理
追踪Collections的
public static <T> void sort(List<T> list, Comparator<? super T> c)
到
public static <T> void sort(T[] a, Comparator<? super T> c)
到
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c)
可以发现其中代码如下:
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排序原理。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
本文实例分析了C#数组反转与排序的方法。分享给大家供大家参考。具体实现方法如下: C#数组反转 代码如下:using System; using System.Collections.Generic; using System.Linq; using System.Text; ...
字符串数组 排序
但是通常排序算法不得不让程序员在写代码的过程中陷入对底层很多指针和位置的理解,java不希望这样,所以排序大多可以由java帮你做掉,例如,你要对一个数组排序,通过:Collections.sort(list)那么这个list被排序了...
数组有工具类Arrays,集合也有一个工具类Collections,这里练习一下集合工具类的排序方法,顺便过一下sort排序方法,比较器。 sort方法 sort(List<T> list):根据其元素的natural ordering对指定的列表进行排序。 ...
主要介绍了Java 生成随机字符串数组的实例详解的相关资料,主要是利用Collections.sort()方法对泛型为String的List 进行排序,需要的朋友可以参考下
//对list数组进行自然排序 Collections.sort(list); //依次检索输出list的所有对象 // for(int i=0;i<list.size();i++){ // System.out.println(list.get(i)); // } Iterator Iter=list.iterator(); while...
比如对一个数组进行排序,程序员可以写如下排序算法: 代码演示:数组排序 public static void sort(int[] arrs) { boolean isSwap = false; for (int i = 0; i ; i++) { isSwap = false; for (int j = arrs....
集合就如同数组,用来存储和管理一组特定类型的数据对象,除了基本的数据处理功能,集合直接提供了各种数据结构及算法的实现,如队列、链表、排序等,可以让你轻易地完成复杂的数据操作。在使用数组和集合时要先...
支持通用列表和序列化属性数组,尽管可以通过实现Rotorz.Games.Collections.IReorderableListAdaptor来支持其他集合类型。 $ yarn add rotorz/unity3d-reorderable-list 该软件包与工具兼容。 有关将程序包同步...
容器是Java编程的一大利器,常用的类是:ArrayList (List)作为可变长数组、HashMap(Map)用来建立查找表,Set很少用,只在HashMap的使用中连带用过一些。通过对这两个类的熟悉,能够将List、Set和Map三大类的基本用法...
数组排序 多维数组 命令行参数 面向对象编程 面向对象基础 方法 构造方法 方法重载 继承 多态 抽象类 接口 静态字段和静态方法 包 作用域 classpath和jar 模块 Java核心类 字符串和编码 ...
数据结构与算法(C#).PDF及代码 第1章 Collections类、泛型类和Timing类概述 第2章 数组和ArrayList 第3章 基础排序算法 第4章 基础查找算法 第5章 栈和队列 第6章 BitArray类 第7章 字符串、String类和StringBuioder...
排序:Comparable Comparator Collections.sort() ArrayList:底层用数组实现的List 特点:查询效率高,增删效率低 轻量级 线程不安全 LinkedList:底层用双向循环链表 实现的List 特点:查询效率低,增删效率高 ...
Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
3.如果列表中的元素是可比较大小的,则可用Java.util.Collections类中的静态方法sort(列表)方法进行排序 Collections.sort(list); System.out.println(list); ;4.求最大最小值 Collections类中的静态方法max(列表)...
96、Hibernate工作原理及为什么要用? 22 97、Hibernate是如何延迟加载? 22 98、Hibernate中怎样实现类之间的关系?(如:一对多、多对多的关系) 22 99、说下Hibernate的缓存机制 22 100、Hibernate的查询方式 23 101...
//对一个数组进行排序 Collections.reverse() //对一个 LIST Arrays.toString(char [] a) //转换为字符串 charAt(int x) //获取特定索引处的字符length() //字符串长度length //数组大小``` 作为链表的“元素”的...