通过不同的方式实现多字段联合排序效果

多字段排序

最佳实践

发布时间: 2022-10-12

文章字数: 1.5k

阅读时长: 5 分

说到排序让你想起的是冒泡排序法、归并排序法、选择排序法等，但是这个是基础的排序方法，在实际的应用基本用不到，就算用到也是被包装到底层，无需自己的实现。下面就说几种在实际应用中使用到的排序方法。

1. 问题场景

现在需要对一个班级的人员进行排序，排序的规则是优先按照年龄排序，当年龄相等时，采用学生的身高排序。

问题就是这样，你们想到几种排序的方法呢？

2. 通过SQL语句排序

数据库中存储班级学生的信息，包含年龄和身高，通过SQL语句实现，很简单如下：

select * from t_student order by age,height

将查询的结果封装到List集合类集合实现排序。

3. 通过实现Comparable接口

创建实体类实现Comparable接口，实现compareTo方法：

@Data
@NoArgsConstructor
@AllArgsConstructor
@Builder
public class Student implements Comparable<Student> {
    private String name;
    private Integer age;
    private Integer height;

    @Override
    public int compareTo(Student o) {
        // 第一种方式：直接通过age和heigh值比较
        return age.compareTo(o.getAge()) > 0 ? 1 : (age.compareTo(o.getAge()) < 0 ? -1 : Integer.compare(height.compareTo(o.height), 0));
        /* 第二种方式：通过扩大age基数，对age和height求和，进行比较
        Integer current = age * 1000 + height;
        Integer target = o.getAge() * 1000 + o.getHeight();
        return current.compareTo(target);*/
    }
}

测试代码：

// 注意这里使用TreeSet，自动排序
Set<Student> studentSet = new TreeSet<>();
studentSet.add(Student.builder().name("joker").age(20).height(170).build());
studentSet.add(Student.builder().name("david").age(18).height(169).build());
studentSet.add(Student.builder().name("zms").age(36).height(216).build());
studentSet.add(Student.builder().name("cendy").age(20).height(156).build());
System.out.println(studentSet);

compareTo方法实现方式：

第一种方式：直接通过age和heigh值比较，这个就很简单不赘述；
第二种方式：通过扩大age基数，对age和height求和，进行比较，这个方式只能用在可预测取值范围字段的比较，height单位是cm时，最大整数位也就是三位数，所以可以将age扩大1000倍，预留后三为给height。如果用在不可预测取值范围字段的比较，可能会导致进位的问题。此方法慎用。

4. 通过Redis的zset进行排序

对Redis存储数据的结构有一定了解的情况下，都会知道zset有一个分数值（score），可以通过这个分数值来进行排序，但是只支持单一的分数值，对于使用两个字段排序实现是不友好的。

但是变通一下即可，上一种解决方案中的compareTo第二种方式逻辑就可以参考，可以将两个或者多个值按照一定的规则进行转换操作，形成一个值。上一种解决方案就是通过扩大倍数方式，但是存在一个问题就是可能会导致进位的问题。那么怎么解决呢？

此时可以使用二进制的高低位来实现，一个long类型的数值是64位，最后一位是用来表示正负值的，0表示正值，1表示负值。那可用的就是后面的63位，我们可以使用前31位表示学生的年龄，后32位表示学生的身高。

@Component
public class RedisZsetSort {

    @Autowired
    private RedisTemplate<String, String> redisTemplate;

    private String key = "sort_key";

    @PostConstruct // 表示初始化完成后执行此方法
    public void run() {
        addStudent(Student.builder().name("joker").age(20).height(170).build());
        addStudent(Student.builder().name("david").age(18).height(169).build());
        addStudent(Student.builder().name("zms").age(36).height(216).build());
        addStudent(Student.builder().name("cendy").age(20).height(156).build());
        pullStudent();
    }

    public void addStudent(Student student) {
        // 将年龄左移32位，采用"|"运算，实现高位和低位的合并
        long score = 32L << (long) student.getAge() | (long) student.getHeight();
        // 让如zset中（无序放入）
        redisTemplate.opsForZSet().add(key, JSON.toJSONString(student), score);
    }

    public void pullStudent() {
        // 从zset中取出数据
        Set<ZSetOperations.TypedTuple<String>> result = redisTemplate.opsForZSet().rangeByScoreWithScores(key, 0L, Long.MAX_VALUE);
        if (CollectionUtils.isEmpty(result)) return;
        // 输出的数据即是已经排序要的数据
        for (ZSetOperations.TypedTuple<String> stringTypedTuple : result) {
            long score = BigDecimal.valueOf(stringTypedTuple.getScore()).longValue();
            Student student = JSONObject.parseObject(stringTypedTuple.getValue(), new TypeReference<Student>() {
            });
            System.out.println(student + "---分数：" + score);
        }
    }
}

但是这里同样需要注意实际比较值（年龄、身高）是否会超过32bit的最大值，在不同的应用场景，对应的实际比较值是不同的，需要合理的进行设计。

比如现在有3个字段参与比较，其中一个值A最大不超过4095，另外两个值B、C都可能超过了4095，那么此时这三个值分配的bit数量就要相应的发生变化。

我们都知道4095对应的12bit最大值，那么此时这个值给12bit就足够，但是B、C可能会超过4095，给12bit就会出现溢出的问题，需要合理预估B、C的最大值界限，合理分配bit数。

5. 总结

首先通过SQL解决的确很方便，在数据量少的时候用着很舒服，但是存在问题就是频繁的查询数据库，给数据库造成压力，如果数据量较大，还会造成响应速度很慢的问题；
通过implement Comparable实现比较排序，需要查出来所有需要比较的数据，然后在服务器内存中进行计算比较，会占用较大的服务器资源，另外执行效率也很低，不推荐使用，作为了解即可。
通过Redis的zset数据类型和二进制的高低位机制结合实现，首先实现方式较为快速，无需过多的在内存中计算；第二可以达到缓存的效果，降低了对数据库的访问压力，相当于解决了上面两种方式存在的问题；最后就是这种实现B格较高，使用的技术点和思路比较新颖。不管是在面试还是在实际运用中，都能够达到很好的效果。