为什么要排序 ?

在Web的世界里万物都需要排序. 如果列表不能排序, 就很难一眼查找到准确的信息. 同样在逢年过节的餐桌上, 会按照座位的排序来区分长幼尊卑,  即使酒席宴前, 言语中也会对人的社会地位分个三六九等.

本文主要探讨, 用 "Jvav" Api 进行不同数据结构的排序. 以及其实现原理讲解, 那么朋友你真的会 "Jvav" 吗?  

以常见的 Oracle数据库排序来说, 如果不加 order by 从句就是根据隐藏列rowid 进行排序, 不能达到对数据准确检索的目的, 往往数据集的排序会在数据库中进行的. 但我们要实现对 链表,树, 图等复杂数据结果的最终业务排序时, 会用到 Java排序Api, 遥想当初初学编程时, 谁没被冒泡排序困扰过呢? 但写Java WEB CRUD后就很少接触到了.  

比较器排序的优劣

模拟某宝的搜索排名, 先定义一个 Pojo, 用于比较元素属性

import lombok.*;

/**
 * Created by 刷题使我快乐,自律使我自由 !
 * 模仿某宝根据权重决定进行最终展示顺序
 */
@Data
@AllArgsConstructor
public   class MbRelatedWeightResource {

    // 机器学习推荐值 (根据千人千面的用户画像预测)
    private Integer mlRecommended;
    // 曝光价格值 (竞价排名)
    private Integer throughWeight;
    // 热度值 (由某个时间维度的浏览量,收藏数,好评数,复购率计算...)
    private Integer heat;
}

定义 Comparable 内部比较器与 Comparator 外部比较器的接口, 实现某宝的商品搜索排名比较.

import lombok.NoArgsConstructor;
import studey.advance.datastructure.pojo.MbRelatedWeightResource;

import java.util.Collections;
import java.util.Comparator;
import java.util.Objects;

/**
 * Created by 分别使用以下两种比较器接口进行元素比较排序
 *
 * @see java.lang.Comparable 该后缀 -able 表明该对象只能用于同一类型之间内部比较
 * @see java.util.Comparator 该后缀 -or   表明该对象可以用于不同类型之间外部    比较
 */
public class ComparerSortRecursion {

    public static class RelatedWeightComparable extends MbRelatedWeightResource implements Comparable<MbRelatedWeightResource> {

        public RelatedWeightComparable(Integer mlRecommended, Integer throughWeight, Integer heat) {
            super(mlRecommended, throughWeight, heat);
        }

        /**
         * 根据规则进行排序
         *
         * @param o 与当前对象比较的同类元素
         * @return 降序比较结果 小于返回正数; 等于返回 0; 大于返回负数;
         */
        @Override
        public int compareTo(MbRelatedWeightResource o) {

            /* 使用卫语句保持代码整洁 */

            // 先比较 千人千面推荐值
            if (!Objects.equals(this.getMlRecommended(), o.getMlRecommended())) {
                return this.getMlRecommended() < o.getMlRecommended() ? 1 : -1;
            }

            // 如果曝光价格值相等再比较
            if (!Objects.equals(this.getThroughWeight(), o.getThroughWeight())) {
                return this.getThroughWeight() < o.getThroughWeight() ? 1 : -1;
            }

            // 如果推荐值相等再比较曝光价格值
            if (!Objects.equals(this.getHeat(), o.getHeat())) {
                return this.getHeat() < o.getHeat() ? 1 : -1;
            }

            return 0;
        }
    }

    @NoArgsConstructor
    public static class RelatedWeightComparator implements Comparator<MbRelatedWeightResource> {

        /**
         * 根据规则进行排序
         *
         * @param o1 泛型对象1
         * @param o2 泛型对象2
         * @return 降序比较结果 小于返回正数; 等于返回 0; 大于返回负数;
         */
        @Override
        public int compare(MbRelatedWeightResource o1, MbRelatedWeightResource o2) {
            // 先比较 千人千面推荐值
            if (!Objects.equals(o1.getMlRecommended(), o2.getMlRecommended())) {
                return o1.getMlRecommended() < o2.getMlRecommended() ? 1 : -1;
            }

            // 如果曝光价格值相等再比较
            if (!Objects.equals(o1.getThroughWeight(), o2.getThroughWeight())) {
                return o1.getThroughWeight() < o2.getThroughWeight() ? 1 : -1;
            }

            // 如果推荐值相等再比较曝光价格值
            if (!Objects.equals(o1.getHeat(), o2.getHeat())) {
                return o1.getHeat() < o2.getHeat() ? 1 : -1;
            }

            return 0;
        }

        @Override
        public Comparator<MbRelatedWeightResource> reversed() {
            return Collections.reverseOrder(this);
        }
    }
}

执行相关单元测试.

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import studey.advance.basearithmetic.sort.ComparerSortRecursion;
import studey.advance.datastructure.pojo.MbRelatedWeightResource;
import studey.advance.datastructure.utils.JsonUtil;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by 分别使用以下两种比较器接口进行元素比较排序的单元测试
 */
class ComparerSortRecursionTest extends ComparerSortRecursion {

    @Test
    @DisplayName("根据内部比较器从大到小排序")
    void comparableCompareTo() {

        ArrayList<RelatedWeightComparable> comparableToList = new ArrayList<>();
        comparableToList.add(new RelatedWeightComparable(100, 51, 20));
        comparableToList.add(new RelatedWeightComparable(101, 1, 1));
        comparableToList.add(new RelatedWeightComparable(100, 50, 20));
        comparableToList.add(new RelatedWeightComparable(100, 51, 21));
        Collections.sort(comparableToList);
        System.out.println(JsonUtil.toJson(comparableToList));
    }

    @Test
    @DisplayName("根据外部比较器从大到小排序")
    void comparatorCompareTo() {
        List<MbRelatedWeightResource> comparatorList = new ArrayList<>();
        comparatorList.add(new MbRelatedWeightResource(100, 51, 20));
        comparatorList.add(new MbRelatedWeightResource(101, 1, 1));
        comparatorList.add(new MbRelatedWeightResource(100, 50, 20));
        comparatorList.add(new MbRelatedWeightResource(100, 51, 21));
        comparatorList.sort(new RelatedWeightComparator());
        System.out.println(JsonUtil.toJson(comparatorList));
    }
}

运行这两个基本单元测试没啥问题, 但一般真实业务场景会在for循环中进行子排序, 来迭代子列表结构!

 @Test
    @DisplayName("根据lambda比较器从大到小排序")
    void comparatorChildListSort() throws InterruptedException {
        List<MbRelatedWeightResource> comparatorList = new ArrayList<>();
        comparatorList.add(new MbRelatedWeightResource(100, 51, 20));
        comparatorList.add(new MbRelatedWeightResource(101, 1, 1));
        comparatorList.add(new MbRelatedWeightResource(100, 50, 20));
        comparatorList.add(new MbRelatedWeightResource(100, 51, 21));

        for (MbRelatedWeightResource relatedWeightComparable : comparatorList) {
            // 迭代器和增强for循环遍历时排序会 ConcurrentModificationException
            compareToList.sort(new ComparerSortRecursion.RelatedWeightComparator());
        }
        System.out.println(JsonUtil.toJson(comparatorList));
    }

这次的for循环排序单元测试就抛出 ConcurrentModificationException.

java.util.ConcurrentModificationException  at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)  at java.util.ArrayList$Itr.next(ArrayList.java:851) at advance.basearithmetic.sort.ComparerSortRecursionTest.comparatorChildListSort (ComparerSortRecursionTest.java:45)

at java.util.ArrayList.forEach(ArrayList.java:1249)

我们 debug 一下 Exception 源码 !

public class ArrayList<E> extends AbstractList<E> ... {
 /** 字段在AbstractList父类中, 为了方便演示 copy, 以下为jdk源码注释
 该字段用于iterator和list iterator方法返回的迭代器和列表迭代器实现。
 如果这个字段的值变化出乎意料,迭代器(或列表迭代器)将抛出一个并发修改异常在代码下,
 代码删除,代码之前,代码集或代码添加操作。这提供了fail - fast行为，
 而不是在迭代期间面对并发修改时的非确定性行为。
 */
    protected transient int modCount = 0;
    
    public E next() {
         checkForComodification();
         ...  
    }

    private class Itr implements Iterator<E> {

      int expectedModCount = modCount;

      final void checkForComodification() {
          if (modCount != expectedModCount)
           throw new ConcurrentModificationException();
    }
}

modCount 的其余注解, 子类使用这个字段是可选的。如果希望一个子类提供快速失败迭代器,那么它仅仅增加这个字段的(int, E)和删除方法(和任何其他方法,它将覆盖,导致结构修改列表)。对 add (int, E)或 code remove (int)的单个调用必须在该字段中添加一个以上的值，否则迭代器(和列表迭代器)将抛出伪造的 code并发修改异常。如果实现不希望提供快速失败迭代器，则可以忽略此字段。

单元测试调用了 next() 方法后就报错了!

异常原因, Iterator 是依赖于 AbstractList 而存在的，在判断成功后，在 ArrayList 的中新添加了元素，而迭代器却没有同步，所以就抛出了 ConcurrentModificationException 。意思是 Iterator 以及语法糖(增强for循环)遍历元素的时候，不能修改的此类集合. 比如ArrayList,LinkedList,HashMap 等不忽略modCount 字段的数据结构。

如果是使用 for 循环与 lambda 语法就可以成功运行.

 for (MbRelatedWeightResource relatedWeightComparable : compareToList) {
            // 迭代器和增强for循环遍历时排序会 ConcurrentModificationException
            // lambda 排序则能运行
     comparatorList = comparatorList.stream().sorted(
         Comparator.comparing(MbRelatedWeightResource::getMlRecommended)                          .thenComparing(MbRelatedWeightResource::getThroughWeight)
         .thenComparing(MbRelatedWeightResource::getHeat).reversed())
         .collect(Collectors.toList());
 }

最终三个单元测试统一输出

综上所述, Comparable 是不推荐的, 因为对 pojo 的修改容易难以维护, 图中使用继承类的方式来做也有点冗余, 而且它的Api过于单一只有 compareTo() 比较函数, 而 Comparator 有小20个排序相关Api, 用到简单业务是可以的.  Comparator 不仅可以用 lambda 表达式进行书写, 同时可以将它注入到 Spring 容器中进行排序. 总之需要多场景执行统一排序规则就维护 Comparator 外部排序器, 如果是单一场景的排序规则就用  lambda  表达式即可! 感谢 JDK 给我们的趁手兵器 !

https://github.com/XiaoZiShan/studey-advance/blob/ffbc804f9cff54aa5529e1b408dabac2eab53449/src/test/java/advance/basearithmetic/sort/ComparerSortRecursionTest.java

Lambda 排序的优劣

先了解 lambda 基本语法

import studey.advance.datastructure.utils.JsonUtil;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by 使用 lambda 语法操作数据
 */
public class LambdaGrammarDemo extends ComparerSortRecursion {

    public static void main(String[] args) {

        // 数据最终结果类型 list or map or set

        // jdk8 之前
        // 对list 进行排序
        List<RelatedWeightComparable> compareToList = new ArrayList<>();
        compareToList.add(new RelatedWeightComparable(101, 1, 1));
        compareToList.add(new RelatedWeightComparable(100, 50, 20));
        compareToList.add(new RelatedWeightComparable(100, 51, 20));
        compareToList.add(new RelatedWeightComparable(100, 51, 21));
        // 调用比较器进行排序
        compareToList.sort(new ComparerSortRecursion.RelatedWeightComparator().reversed());

        // 获取字段组成list
        List<String> strings = new ArrayList<String>();
        for (RelatedWeightComparable relatedWeightComparable : compareToList) {
            strings.add(relatedWeightComparable.getThroughWeight().toString());
        }
        // 只要前3个参数
        List<String> stringx = new ArrayList<String>();

        for (int i = 0; i < 3; i++) {
            stringx.add(strings.get(i));
        }
        System.out.println(JsonUtil.toJson(stringx));
        Set sf = new HashSet<>(stringx);

        // 再转成map ，回到第一步，麻烦


        // java8 lambda 表达式
        compareToList.sort(RelatedWeightComparable::compareTo);

        JsonUtil.toJson(compareToList.stream().sorted(Comparator.comparing(RelatedWeightComparable::getHeat).thenComparing(RelatedWeightComparable::getMlRecommended))
            .map(RelatedWeightComparable::getThroughWeight).limit(3).collect(Collectors.toList()));

        System.out.println(
            JsonUtil.toJson(compareToList.stream().sorted(Comparator.comparing(RelatedWeightComparable::getHeat).thenComparing(RelatedWeightComparable::getMlRecommended)).
                limit(3).collect(Collectors.toMap(RelatedWeightComparable::getThroughWeight, RelatedWeightComparable::getHeat))));

        compareToList.forEach(v -> {
            v.setHeat(1);
            v.setThroughWeight(0);
        });

        System.out.println(JsonUtil.toJson(compareToList.stream().map(v -> {
            v.setMlRecommended(9);
            return v;
        }).collect(Collectors.toList())));
    }
}

lambda 花式排序

import studey.advance.datastructure.pojo.MbRelatedWeightResource;

import java.util.List;
import java.util.stream.Collectors;

import static java.util.Comparator.*;

/**
 * Created by 使用 lambda 语法进行元素比较排序
 */
public class LambdaSortRecursion  {
    // lambda 实现比较器的排序方式
    public List<MbRelatedWeightResource> lambdaSort(List<MbRelatedWeightResource> mbList){
        return  mbList.stream().sorted(comparing(MbRelatedWeightResource::getMlRecommended)
            .thenComparing(MbRelatedWeightResource::getThroughWeight)
            .thenComparing(MbRelatedWeightResource::getHeat)).collect(Collectors.toList());
    }

    // lambda 反转当前集合顺序
    public List<MbRelatedWeightResource> lambdaReversalSort(List<MbRelatedWeightResource> mbList){
        return  mbList.stream().sorted(comparing(MbRelatedWeightResource::getMlRecommended)
            .thenComparing(MbRelatedWeightResource::getThroughWeight)
            .thenComparing(MbRelatedWeightResource::getHeat).reversed()).collect(Collectors.toList());
    }

    // lambda 兼容 Comparable
    public List<ComparerSortRecursion.RelatedWeightComparable> lambdaComparableSort(List<ComparerSortRecursion.RelatedWeightComparable> mbList){
        return mbList.stream().sorted(ComparerSortRecursion.RelatedWeightComparable::compareTo).collect(Collectors.toList());
    }

    // lambda 兼容 Comparator
    public List<MbRelatedWeightResource> lambdaComparatorSort(List<MbRelatedWeightResource> mbList){
        return mbList.stream().
            sorted(comparing(e -> e, new ComparerSortRecursion.RelatedWeightComparator())).collect(Collectors.toList());
    }
}

https://github.com/XiaoZiShan/studey-advance/blob/80cd97d97f5667e043b3a16bc9fa44cf0ecc4fbb/src/test/java/advance/basearithmetic/sort/LambdaSortRecursionTest.java

综上所述, 排序对 lambda 来说是一件比较擅长的事情, 它的底层到底是怎么实现的呢 ?  我们先从分析 lambda 的语法来开始理解它吧 ! 以上述lambda反转当前集合的代码为例子.

// 以下注释基本来源于相关jdk源码
mbList
// 返回一个被创建的连续流，该 mbList 集合作为其源。
    .stream()
// 返回一个由该流的元素组成的流，根据提供的{@ code Comparator}排序。对于stream()有序流，排序是稳定的。对于parallelStream()无序流，不做稳定性保证。    
    .sorted(
    // 用 Comparator 的lambda风格api构建比较器
    comparing(MbRelatedWeightResource::getMlRecommended)
           ..thenComparing(...)
           .reversed())
    // 封装流处理后的返回结构
    .collect(Collectors.toList());

lambda 流式排序原理参考.

Collector是专门用来作为Stream的collect方法的参数的。

相关文章 https://blog.csdn.net/qq_40660787/article/details/109579574

关于 lambda 排序性能分析 https://blog.csdn.net/weixin_40834464/article/details/107874710

下一篇技术博客将深入 lambda 原理.

Java排序原理解析

    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

美国程序员 TimPeter 结合了归并排序和插入排序的优点, 实现了 TimSort 排序算法, 避免了归并排序与插入排序的缺点,相比以往的归并排序, 减少了归并次数, 相比插入排序, 引入了二分查找的概念, 提高了排序效率. 对于部分排序数组, 平均时间复杂度最优可达 O(n); 对于随机排序的数组, 时间复杂度为 O(nlogn), 平均时间复杂度 O(nlogn), JDK 中 TimSort 取代了原先的归并排序.

总结

其实比较器们不仅可以用于排序, 还可以用于分组, 如果两者相等则归为一组. JDK 的优美在于每一个版本的优美扩展, 1.2 时创建 java.lang.Comparable , java.util.Comparator , 一个负责内部排序, 扩展时无需考虑. 一个负责外部排序, 在1.8 时增强了多个api, 使得与 lambda 无缝进行扩展, 使JDK得以上下兼容 ,这或许就是编程的魅力吧 !阅读优秀源码, 有益编码健康!