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

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

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

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

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

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中只有一个方法

Java代码

public int compareTo(T o);

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

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

2.3 自定义类的比较

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

Java代码

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代码:

Herry    19
Herry    20
Jack    19
James    18
James    19
Jim   19
Luccy    19
Lucy    19

可以看出只需两点即可

a、继承自Comparable

Java代码

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代码

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代码

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

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

追踪Collections的

Java代码

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

Java代码

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

Java代码

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

可以发现其中代码如下:

Java代码

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排序原理就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • java 对象数组排序

    废话不多说直接奉上代码先: import java.util.*; import java.io.*; public class Main{ static int [] dp = new int [1010]; public static void main(String [] args)throws IOException{ Mouse [] mice = new Mouse [1010]; FileReader fr=new FileReader("in.txt"); //读取文件

  • Java中集合和数组的排序方式小结

    根据约定,在使用java编程的时候应尽可能的使用现有的类库,当然你也可以自己编写一个排序的方法,或者框架,但是有几个人能写得比JDK里的还要好呢?使用现有的类的另一个好处是代码易于阅读和维护,这篇文章主要讲的是如何使用现有的类库对数组和各种Collection容器进行排序,(文章中的一 部分例子来自<Java Developers Almanac 1.4>) 首先要知道两个类:java.util.Arrays和java.util.Collections(注意和Collection的区 别)Co

  • 用Java集合中的Collections.sort方法如何对list排序(两种方法)

    第一种是list中的对象实现Comparable接口,如下: /** * 根据order对User排序 */ public class User implements Comparable <user> { private String name; private Integer order; public String getName() { return name; } public void setName(String name) { this.name = name; } publi

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

    常需要对list进行排序,小到List<String>,大到对自定义的类进行排序.不需要自行归并或堆排序.简单实现一个接口即可. 本文先会介绍利用Collections对List<String>进行排序,继而讲到Collections.sort的原理, 再讲到如何对自定义类进行排序, 最后会介绍利用Collections sort对自定义对象进行排序的另外一种方法,并将两种排序进行了简单的性能比较. 1.对List<String>排序及Collections.sort的

  • 浅谈numpy数组的几种排序方式

    简单介绍 NumPy系统是Python的一种开源的数组计算扩展.这种工具可用来存储和处理大型矩阵,比Python自身的嵌套列表(nested list structure)结构要高效的多(该结构也可以用来表示矩阵(matrix)). 创建数组 创建1维数组: data = np.array([1,3,4,8]) 查看数组维度 data.shape 查看数组类型 data.dtype 通过索引获取或修改数组元素 data[1] 获取元素 data[1] = 'a' 修改元素 创建二维数组 data

  • 浅谈Java数组的一些使用方法及堆栈存储

    数组 用于存储一组同一数据类型数据的容器 数组会对放入其中的数据自动编号,编号是从0开始的---下标 定义格式 数据类型[] 数组名 = new 数据类型[数组的大小];---可以先声明再初始化 int[] arr = new int[5];---定义了一个最多能存储5的整数的数组 arr[3] = 4; arr[3]---通过数组名[下标]的形式来获取数组元素或者给对应的位置赋值 数据类型[] 数组名 = new 数据类型[]{元素1,元素2--}; int[] arr = new int[]

  • 浅谈C#数组(一)

    目录 一.简单数组之一维数组 1.数组的声明 2.数组的初始化 3.访问数组元素 4.数组中使用引用类型 二.多维数组 三.锯齿数组 四.Array类 1.创建数组 2.复制数组 3.排序 五.数组作为参数 1.数组协变 2.ArraySegment<T> 前言: 如果需要使用同一类型的多个对象,可以使用数组和集合.C#用特殊的记号声明,初始化和使用数组.Array类在后台发挥作用,它为数组中的元素排序和过滤提供了多个方法.使用枚举器,可以迭代数组中的所有元素. 如果需要使用不同类型的多个对象

  • 浅谈js数组和splice的用法

    首先添加一个splice函数: splice:该方法的作用就是从数组中删除一个元素 array.splice(index,count,value....); index:表示从哪一个下标开始, count:表示删除元素的个数 value:代表增加的元素 example: 1.var array = new Array(1,2,3,4,5,6); array.splice(0,1,2) result:2,2,3,4,5 2.var array = new Array(1,2,3,4,5,6); a

  • 浅谈Go数组比切片好在哪

    目录 数组是什么 切片是什么 数组的优势 可比较 编译安全 长度是类型 规划内存布局 访问速度 总结 参考 前段时间有播放一条快讯,就是 Go1.17 会正式支持切片(Slice)转换到数据(Array),不再需要用以前那种骚办法了,安全了许多. 但是也有同学提出了新的疑惑,在 Go 语言中,数组其实是用的相对较少的,甚至会有同学认为在 Go 里可以把数组给去掉. 数组相较切片到底有什么优势,我们又应该在什么场景下使用呢? 这是一个我们需要深究的问题,因此今天就跟大家一起来一探究竟,本文会先简单

  • 浅谈C#数组(二)

    目录 一.枚举集合 1.IEnumerator接口 2.foreach语句 3.yield语句 二.元组(Tuple) 三.结构比较 可以先了解上一篇文章内容C#数组(一) 一.枚举集合 在foreach语句中使用枚举,可以迭代集合中的元素,且无需知道集合中元素的个数.foreach语句使用一个枚举器.foreach会调用实现了IEnumerable接口的集合类中的GetEumerator()方法.GetEumerator()方法返回一个实现IEnumerator接口的对象枚举.foreach语

  • 浅谈JS数组内置遍历方法有哪些和区别

    目录 forEach()(ES6)方法 map()(ES6) 方法 flatMap()方法 for...in... for...of... filter(ES6)遍历数组 every()函数(ES6) find()函数(ES6) findIndex()函数 (ES6) forEach()(ES6)方法 forEach()(ES6)方法对数组的每个元素执行一次给定的函数. 1. 数组里的元素个数有几个,该方法里的回调就会执行几次     2. 第一个参数是数组里的元素,第二个参数为数组里元素的索引

  • 浅谈$_FILES数组为空的原因

    今天做上传的文件时候,打印$_files总是为空,查阅了下资料. 发现是 max_file_uploads=0 知道了原因 file_uploads = On upload_max_filesize = 20M max_file_uploads = 20 以上这篇浅谈$_FILES数组为空的原因就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们.

  • JavaScript对象数组如何按指定属性和排序方向进行排序

    引子 在以数据为中心的信息系统中,以表格形式展示数据是在常见不过的方式了.对数据进行排序是必不可少的功能.排序可以分为按单个字段排序和按多个字段不同排序方向排序.单字段排序局限性较大,不能满足用户对数据的关注点变化的需求,而多字段排序就可以较好的弥补这个缺陷. 多字段排序,实现的方式从大的层面上可以分为后端实现和前端实现. 后端排序 后端实现排序可以在数据库层面实现或者在应用程序层面实现. 数据库层面实现多字段排序非常简单,使用SQL的排序指令"Order By"即可--Order B

随机推荐