如何优雅地给List集合排序

Lvshen

发布于 2022-05-05 19:39:30

1.7K0

发布于 2022-05-05 19:39:30

文章被收录于专栏：Lvshen的技术小屋Lvshen的技术小屋

在平时的开发中，我们或多或少的会用到排序。在最开始学习语言的时候，我们都会学习基本的排序算法。例如：冒泡排序，基数排序，快速排序，插入排序，选择排序。

现在我们开发时一般使用Java自带的排序方法给集合排序，不用自己写排序算法了。例如在List集合中我们我们可以使用Collections.sort(list)排序。

简单集合

我们有一个String元素的List，排序方式如下：

@Test
public void testString() {
    List<String> stringList = Arrays.asList("Lvshen", "Zhouzhou", "Alan");
    Collections.sort(stringList);
    Console.log(stringList);
}

如上图，我们发现集合按首字母排好序了。

那你是否对Collections.sort()如何排序感兴趣呢，我们扒一下sort()的源码：

“注：jdk1.7后LegacyMergeSort.userRequested=false ”

发现里面用到了ComparableTimSort.sort，底层属于归并排序。

“归并排序（Merge Sort）：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。归并排序是一种稳定的排序算法。 ”

从上面我们知道，归并排序将数组拆分成了两段，每段递归的进行归并排序，在将这两段合并起来。

ComparableTimSort.sort实际并不完全算归并排序了，这里的算法做了很多优化，结合了归并排序和插入排序。以实现更好的性能。

复杂对象集合

在大多数情况下我们的集合元素可能是个复杂对象。例如有一个运动员对象，里面有姓名，身高属性。那如何根据特定的属性排序呢？

@Data
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class Sportsman {
    private String name;
    /**
     * 身高 cm
     */
    private Integer height;
}

这里我们可以使用Comparator.comparing方法进行排序。

@Test
public void test1() {
    sportsmen.sort(Comparator.comparing(Sportsman::getName));
    Console.log(sportsmen);
}

运行结果如下：

查看源码我们发现Comparator.comparing内部使用了compareTo。

而list.sort的排序如下所示：

里面用到了TimSort.sort功能和ComparableTimSort.sort一样，不同之处在于TimSort.sort接收了自定义比较器Comparator c。

Comparator.comparing内部使用了compareTo，那么我们是否可以自定义使用compareTo方法呢。例如在Sportsman对象中，我们先按姓名进行第一排序，如果姓名相同，再按身高进行第二排序。上面的方法显然不适用，这时我们需要自定义比较方法了。

首先我们需要在Sportsman对象内定义一个比较方法：

public static int compareByNameThenHeight(Sportsman s1, Sportsman s2) {
    if (s1.name.equals(s2.name)) {
        return Integer.compare(s1.height, s2.height);
    } else {
        return s1.name.compareTo(s2.name);
    }
}

上面的代码就是先比较name，如果name相同，再比较height。

定义好方法后，使用如下：

@Test
public void test2() {
    sportsmen.add(new Sportsman("Alan", 165));
    Console.log("比较前：【{}】", sportsmen.toString());
    sportsmen.sort(Sportsman::compareByNameThenHeight);
    Console.log("比较后：【{}】", sportsmen.toString());
}

排序结果如上。

如果你不想写在类中，也可以直接写在sort方法中：

@Test
public void test3() {
    sportsmen.add(new Sportsman("Alan", 165));
    Console.log("比较前：【{}】", sportsmen.toString());
    sportsmen.sort((s1, s2) -> {
        if (s1.getName().equals(s2.getName())) {
            return Integer.compare(s1.getHeight(), s2.getHeight());
        } else {
            return s1.getName().compareTo(s2.getName());
        }
    });

    Console.log("比较后：【{}】", sportsmen.toString());
}

sort中可以使用Lambda表达式。

其实我们也不必自己定义排序方法，Java中也有方法可以实现多属性的排序。方法为：java.util.Comparator#thenComparing(java.util.function.Function<? super T,? extends U>)

使用如下：

@Test
public void test4() {
    sportsmen.add(new Sportsman("Alan", 165));
          sportsmen.sort(Comparator.comparing(Sportsman::getName).thenComparing(Sportsman::getHeight));
    Console.log("over");
}

Java8的排序

java8的stream也很好的支持了排序。如果我们要对姓名倒叙排序，可以使用如下方法：

@Test
public void test5() {
    final List<Sportsman> sortedSportsman = sportsmen.stream()
            .sorted(Comparator.comparing(Sportsman::getName, Comparator.reverseOrder()))
            .collect(Collectors.toList());

    Console.log("over");
}

排序结果如上图，实现了name的倒序。

如果集合中的元素有null值，使用Comparator.comparing会报空指针异常，

@Test
public void sortedNull() {
    final List<Sportsman> sportsmen = Lists.newArrayList(
            null,
            new Sportsman("ghost", 120),
            null
    );
    sportsmen.stream()
            .sorted(Comparator.comparing(Sportsman::getName).reversed())
            .collect(Collectors.toList());
    Console.log("test is over");
}

报错信息：

这时需要使用Comparator.nullsLast。

@Test
public void sortedNullLast() {
    final List<Sportsman> sportsmen = Lists.newArrayList(
            null,
            new Sportsman("ghost", 120),
            null
    );
     sportsmen.sort(Comparator.nullsLast(Comparator.comparing(Sportsman::getName)));
   
   Console.log("test is over");
}