java如何给对象按照字符串属性进行排序

目录
  • 给对象按照字符串属性进行排序
  • 三种方法实现字符串排序
    • 排序方法概述
    • 键索引计数法
    • 低位优先的字符串排序(LSD)
    • 高位优先的字符串排序(MSD)
    • 三向字符串快速排序

给对象按照字符串属性进行排序

在java中对象进行排序,排序的属性是string,我们只需要实现Comparator接口,然后实现比较的方式。

public class StringSort {
    public static void main(String[] args) {

        test1();

    }

    // 方式1:
    public static void test1(){
        JSONObject jsonObject = JSONObject.parseObject("{\"result\":[{\"id\":\"A1001\",\"text\":\"程序员\"}, {\"id\":\"G1003\",\"text\":\"建筑师\"}, {\"id\":\"D1005\",\"text\":\"设计师\"}, {\"id\":\"G1009\",\"text\":\"自由职业\"}, {\"id\":\"E2007\",\"text\":\"学生\"}, {\"id\":\"C1009\",\"text\":\"教师\"}, {\"id\":\"A1002\",\"text\":\"医生\"}, {\"id\":\"B1005\",\"text\":\"律师\"}, {\"id\":\"F2009\",\"text\":\"架构师\"}]}");
        List<JSONObject> list = JSONArray.parseArray(jsonObject.getString("result"), JSONObject.class);

        list.forEach(System.out::println);

        Collections.sort(list, new Comparator<JSONObject>() {
            @Override
            public int compare(JSONObject o1, JSONObject o2) {
                 return  o1.getString("id").compareTo(o2.getString("id") ); // 升序排列
//                return  - o1.getString("id").compareTo(o2.getString("id") ); // 降序排列
            }
        });

        System.out.println("--------------排序后--------------------");

        list.forEach(System.out::println);
    }

    // 方式2:
    public  static void test2(){
        JSONObject jsonObject = JSONObject.parseObject("{\"result\":[{\"id\":\"A1001\",\"text\":\"程序员\"}, {\"id\":\"G1003\",\"text\":\"建筑师\"}, {\"id\":\"D1005\",\"text\":\"设计师\"}, {\"id\":\"G1009\",\"text\":\"自由职业\"}, {\"id\":\"E2007\",\"text\":\"学生\"}, {\"id\":\"C1009\",\"text\":\"教师\"}, {\"id\":\"A1002\",\"text\":\"医生\"}, {\"id\":\"B1005\",\"text\":\"律师\"}, {\"id\":\"F2009\",\"text\":\"架构师\"}]}");
        List<JSONObject> list = JSONArray.parseArray(jsonObject.getString("result"), JSONObject.class);

        list.forEach(System.out::println);

        Collections.sort(list, (o1, o2) -> {
            // return   o1.getString("id").compareTo(o2.getString("id") ); // 升序排列
            return  - o1.getString("id").compareTo(o2.getString("id") ); // 降序排列
        });

        System.out.println("--------------排序后--------------------");

        list.forEach(System.out::println);
    }

    // 方式3:
    public  static void test3(){
        JSONObject jsonObject = JSONObject.parseObject("{\"result\":[{\"id\":\"A1001\",\"text\":\"程序员\"}, {\"id\":\"G1003\",\"text\":\"建筑师\"}, {\"id\":\"D1005\",\"text\":\"设计师\"}, {\"id\":\"G1009\",\"text\":\"自由职业\"}, {\"id\":\"E2007\",\"text\":\"学生\"}, {\"id\":\"C1009\",\"text\":\"教师\"}, {\"id\":\"A1002\",\"text\":\"医生\"}, {\"id\":\"B1005\",\"text\":\"律师\"}, {\"id\":\"F2009\",\"text\":\"架构师\"}]}");
        List<JSONObject> list = JSONArray.parseArray(jsonObject.getString("result"), JSONObject.class);

        list.forEach(System.out::println);

        Collections.sort(list, Comparator.comparing(o -> o.getString("id")));

        System.out.println("--------------排序后--------------------");

        list.forEach(System.out::println);
    }

}

三种方法实现字符串排序

排序方法概述

对于许多应用,决定顺序的键都是字符串。本篇讲述如何利用字符串的特殊性质来对其进行高效的排序。

  • 第一类方法会从右到左检查键中的字符。这种方法一般被称为低位优先(Least-Significant-DigitFirst,LSD)的字符串排序。如果将一个字符串看做一个256进制的数字,那么从右向左检查字符串就等价于先检查数字的最低位。这种方法最适合用于键的长度都相同的字符串排序应用。
  • 第二类方法会从左到右检查键中的字符,首先查看的是最高位的字符。这种方法通常称为高位优先(MSD)的字符串排序。高位优先的字符串排序和快速排序类似,因为它们都会将需要排序的数组切分为独立的部分并递归地用相同的方法处理子数组来完成排序。它们的区别之处在于高位优先的字符串排序算法在切分时仅使用键的第一个字符,而快速排序的比较则会涉及键的全部。
  • 第三种方法是高位优先的字符串排序算法的改进快速排序,根据键的首字母进行三向切分,仅在中间子数组中的下一个字符(因为键的首字母都与切分字符相等)继续递归排序。

键索引计数法

作为热身,我们先学习一种适用于小整数键的简单排序方法。这种叫做键索引计数的方法本身就很实用,同时也是要学习的三种排序算法中前两种的基础。它其实就桶计数。

现在来情景引入,老师在统计学生的分数时可能会遇到以下数据处理问题。学生被分为若干组,标号为1、2、3、4等。在某些情况下,我们希望将全班同学按组分类。因为组的编号是较小的整数,使用键索引计数法来排序时很合适的。假设数组a[]中的每个元素都保存了一个名字和一个组号,其中组号在0到R-1之间,代码a[i].key()会返回指定学生的组号。四个步骤见代码

int N = a.length;
int R = 256;    //R为字符基数

String[] aux = new String[N];
int[] count = new int[R + 1];

//计算出现频率
for (int i = 0; i < N; i++) 
    count[a[i].key() + 1]++;

//将频率转换为索引
for (int r = 0; r < R; r++) 
    count[r + 1] += count[r];

//将元素分类
for (int i = 0; i < N; i++) 
    aux[count[a[i].key()]++] = a[i];

//回写
for (int i = 0; i < N; i++)
    a[i] = aux[i];

命题A:键索引计数法排序N个键为0到R-1之间的整数的元素需要访问数组11N+4R+1次

低位优先的字符串排序(LSD)

如果字符串的长度均为W,那就从右向左以每个位置的字符作为键,用键索引计数法将字符串排序W遍。

命题B:低位优先的字符串排序算法能够稳定地将定长字符串排序

class LSD{
    // Least-Significant-Digit First
    //低位优先的字符串排序(基数排序)
    public static void sort(String[] a, int W) {
        //通过前W个字符将a[]排序
        int N = a.length;
        int R = 256;    //基数
        String[] aux = new String[N];  //辅助数组\

        for(int d = W - 1; d >= 0; d--) {
            //根据第d个字符用键索引计数法排序
            int[] count = new int[R + 1];   
            //计算出现频率
            for (int i = 0; i < N; i++)
                count[a[i].charAt(d) + 1]++;
            //将频率转换为索引
            for (int r = 0; r < R; r++)
                count[r + 1] += count[r];
            //将元素分类
            for (int i = 0; i < N; i++) 
                aux[count[a[i].charAt(d)]++] = a[i];
            //回写
            for (int i = 0; i < N; i++) 
                a[i] = aux[i];
        }
    }
}

在许多字符串排序的应用中,键的长度可能互不相同。改进后的低位优先的字符串排序是可以适应这些情况的。下来讲解两种处理变长键排序的算法

高位优先的字符串排序(MSD)

首先用键索引计数法将所有字符串按照首字母排序,然后(递归地)再将每个首字母所对应的子数组排序(忽略首字母,因为每一类中的所有首字母都是相同的)。和快速排序一样,高位优先的字符串排序会将数组切分为能够独立排序的子数组来完成排序任务,但它的切分会为每个首字母得到一个子数组,而不是像快速排序中那样产生固定的两个或者三个切分。

在高位优先的字符串排序算法中,要特别注意到达字符串末尾的情况。在排序中,合理的做法是将所有字符都已被检查过的字符串所在的子数组排在所有子数组的前面,这样就不需要递归地将该子数组排序。为了简化这两步计算,我们使用了一个接受两个参数的私有方法charAt()来将字符串中字符索引转化为数组索引,当指定的位置超过了字符串末尾时该方法返回-1,。然后将所有返回值加1,得到一个非负的int值并用它作为count[]的索引。这种转换意味着字符串中的每个字符都可能产生R+1种不同的值:0表示字符串的结尾,1表示字符串的第一个字符,2表示字符串的第二个字符,等等。因为建索引计数法本来就需要一个额外的位置,所以使用代码int count[] = new int[R + 2]

class MSD{
    //高位优先的字符串排序
    private static int R = 256;      //基数
    private static final int M = 15; //小数组的切换阈值
    private static String[] aux;     //数组分类的辅助数组
    private static int charAt(String s, int d) {
        if(d < s.length()) {
            return s.charAt(d);
        }else {
            return -1;
        }
    }
    public static void sort(String[] a) {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N - 1, 0);
    }
    private static void sortInsert(String[] a, int lo, int hi) {
        //小型数组进行插入排序
        for (int i = lo + 1; i <= hi; i++) {
            for(int j = i; j > lo && a[j].compareTo(a[j - 1]) < 0; j--) {
                String tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
        }
    }
    private static void sort(String[] a, int lo, int hi, int d) {
        //以第d个字符为键将a[lo]至a[hi]排序
        if(hi <= lo + M) {
            sortInsert(a, lo, hi);
            return; 
        }
        int [] count = new int[R + 2];    //计算频率
        for(int i = lo; i <= hi; i++) {
            count[charAt(a[i], d) + 2]++;
        }
        for(int r = 0; r < R + 1; r++) {  //将频率转换为索引
            count[r + 1] += count[r];
        }
        for(int i = lo; i <= hi; i++) {   //数据分类
            aux[count[charAt(a[i], d) + 1]++] = a[i];
        }
        for(int i = lo; i <= hi; i++) {   //回写
            a[i] = aux[i - lo]; 
        }
        //递归的以每个字符为键进行排序
        for(int r = 0; r <R; r++) {
            sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
        }
    }
}

三向字符串快速排序

我们也可以根据高位优先的字符串排序算法改进快速排序,根据键的首字母进行三向切分,仅在中间子数组的下一个字符(因为键得出首字母都与切分字母相同)继续递归排序。这个算法的实现并不困难,参考往期排序算法中的三向切分快排即可。

尽管排序的方式有所不同,但三向字符串快速排序根据的仍然是键的首字母并使用递归的方法将其余部分排序。对于字符串的排序,这个方法比普通的快速排序和高位优先的字符串排序更友好。实际上,它就是两种算法的结合。

三向字符串快速排序只将数组切分为三部分,因此当相应的高位优先的字符串排序产生的非空切分较多时,它需要移动的数据量就会变大,因此它需要进行一系列的三向切分才能够取得多向切分的效果。但是,高位优先的字符串排序可能会创建大量(空)子数组,而三向字符串快速排序的切分总是只有三个。因此三向字符串快速排序能够很好地处理等值键、有较长公共前缀的键、取值范围较小的键和小数组-----所有高位优先的字符串排序算法不擅长的各种情况。

class Quick3string{
    //三向字符串快速排序
    private static int charAt(String s, int d) {
        if(d < s.length()) {
            return s.charAt(d);
        }
        return -1;
    }
    
    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }
    
    private static void sort(String[] a, int lo, int hi, int d) {
        if(hi <= lo) {
            return;
        }
        int lt = lo, gt = hi, i = lo + 1;
        int v = charAt(a[lo], d);
        while(i <= gt) {
            int t = charAt(a[i], d);
            if(t < v) {
                exch(a, lt++, i++);
            }else if(t > v) {
                exch(a, i, gt--);
            }else {
                i++;
            }
        }
        //a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
        sort(a, lo, lt - 1, d);
        if(v >= 0) {
            sort(a, lt, gt, d + 1);
        }
        sort(a, gt + 1, hi, d);
    }
    
    private static void exch(String[] a, int i, int j) {
        String t = new String(a[i]);
        a[i] = a[j];
        a[j] = t;
    }
}

在将字符串数组a[]排序时,根据它们的首字母进行三向切分,然后(递归地)将得到的三个子数组排序:一个含有所以首字母小于切分字符的字符串子数组,一个含有所以首字母等于切分字符串的子数组(排序时忽略它们的首字母),一个含有所有首字母大于切分字符的字符串的子数组。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Java实现储存对象并按对象某属性排序的几种方法示例

    本文实例讲述了Java实现储存对象并按对象某属性排序的几种方法.分享给大家供大家参考,具体如下: 在编程的时候,经常会出现对某一种类的对象们按照某属性进行自定义的排序,比如:学生对象按照age大小排序. 有一种方法就是把age单独提出来排好序,然后按照ages数组的顺序把students重存一次.但是这样太繁琐了,有没有更好的方法呢? 有滴~ 第一种,可以实现边添加边排序,需要用到TreeSet. 第二种,用数组存放对象们,但是不需单独取出某属性排列好再重存,而是在原数组上用比较器重新排一次序.

  • Java的sort的排序及使用详解

    目录 1.按升序排列: 2. 随机排序: 3.按降序排列: 4.根据参数属性值排序 5. 根据参数不同,来确定是升序排列,还是降序排序 总结 sort() 方法在适当的位置对数组的元素进行排序,并返回数组.数组会按照字符的Unicode进行排序(把数组里面当成字符串处理) 1.按升序排列: var arr=[1,11,2,22,5,4,0]; arr.sort( function(n1,n2){ return n1-n2; }); alert(arr);//[0,1,2,4,5,11,22] 2

  • java实现6种字符串数组的排序(String array sort)

    注意,本文不是字符串排序,是字符串数组的排序. 方法分别是: 1.低位优先键索引排序 2.高位优先建索引排序 3.Java自带排序(经过调优的归并排序) 4.冒泡排序 5.快速排序 6.三向快速排序 时间复杂度: 最慢的肯定是冒泡,O(n的平方) 最快的是快速排序,平均 O(nlogn) 低位优先,O(nW),W是字符串长度,在字符串长度较短情况下和快速排序时间应该很接近 高位优先,O(n) - O(nW) 三向快速排序,O(n) - O(nW) 本文中使用的例子是一个5757行的随机字符串数组

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

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

  • java json不生成null或者空字符串属性(详解)

    大家平时用java对象转json字符串.null或者空字符串属性是不需要生成到json字符串里面的. 如下方式生成,没有使用的属性也会生成json字符串属性. JSONArray jsonarray = JSONArray.fromObject(ecmMessageMap.values()); msgObj = jsonarray.toString(); {"actionType":"","clientIp":"","

  • 关于Java中String创建的字符串对象内存分配测试问题

    一.创建String对象的两种常用方法比较 举例说明 String str1 = "Java天下第一"; //方法1 String str2 = new String("Java天下第一"); //方法2 System.out.println(str1 == str2); //比较地址,false System.out.println(str1 == str2.intern()); //true 区别 2.1 方法1中,首先会去JVM的常量池里查找是否有存储&quo

  • java ArrayList集合中的某个对象属性进行排序的实现代码

    开发中有时候需要自己封装分页排序时,List如何对某一属性排序呢,分享一个小实例,大家共勉,希望能对大家有用,请多多指教. 1.Student的Bean如下: public class Student { private int age; private String name; private String weight; public String getWeight() { return weight; } public void setWeight(String weight) { th

  • Java反射通过Getter方法获取对象VO的属性值过程解析

    这篇文章主要介绍了Java反射通过Getter方法获取对象VO的属性值过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 有时候,需要动态获取对象的属性值. 比如,给你一个List,要你遍历这个List的对象的属性,而这个List里的对象并不固定.比如,这次User,下次可能是Company. e.g. 这次我需要做一个Excel导出的工具类,导出的批量数据是以List类型传入的,List里的对象自然每次都不同,这取决于需要导出什么信息.

  • Java实现对象按照其属性排序的两种方法示例

    本文实例讲述了Java实现对象按照其属性排序的两种方法.分享给大家供大家参考,具体如下: 有时候需要对对象列表或数组进行排序,下面提供两种简单方式: 方法一:将要排序的对象类实现Comparable<>接口. 首先,创建学生类,我们将根据学生成绩对学生进行排序: /** * 学生类 */ class Student implements Comparable<Student>{ String name; int age; int score; public Student(Stri

  • java jackson 将对象转json时,忽略子对象的某个属性操作

    我就废话不多说了,大家还是直接看代码吧~ //父对象 public class user implements java.io.Serializable { @JsonIgnoreProperties(value={"addressId"})//在解析成json时,忽略子属性的addressId字段 private Address address; private String username; //......... } //子对象 public class Address imp

  • Java比较两个对象中全部属性值是否相等的方法

    例如下述Java类: import java.io.Serializable; import java.util.List; public class Bean_Topology implements Serializable { private static final long serialVersionUID = 1L; public static long getSerialversionuid() { return serialVersionUID; } private Long to

  • Java利用反射获取object的属性和值代码示例

    在看反射顺便做个笔记,目前知道的反射的Object都是要有对象的也就是实体Bean. referance:Java反射简易教程 import java.lang.reflect.Field; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * 反射处理Bean,得到里面的属性值 * * @author liulinsen * */ publ

随机推荐

其他