list排序算法（如何优雅地给List排序）
list排序算法（如何优雅地给List排序）从上面我们知道，归并排序将数组拆分成了两段，每段递归地进行归并排序，再将这两段合并起来。归并排序（Merge Sort）：将待排序数据分成两部分，继续将两个子部分进行递归的归并排序；然后将已经有序的两个子部分进行合并，最终完成排序。其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。归并排序是一种稳定的排序算法。那你是否对Collections.Sort()如何排序感兴趣呢，我们扒一下sort()的源码：注：jdk1.7后LegacyMergeSort.userRequested=false发现里面用到了ComparableTimSort.sort，底层属于归并排序。
在平时的开发中，我们或多或少的会用到排序。在最开始学习语言的时候，我们都会学习基本的排序算法。例如：冒泡排序，基数排序，快速排序，插入排序，选择排序。
现在我们开发时一般使用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");
}
使用Comparator.nullsLast，非null元素会排在null元素前面。
如果需要将非null元素排在后面，可以使用Comparator.nullsFirst。
如上图所示，非null元素排在了后面。
今天的文章就写到这里了，如果这篇文章对你有帮助，欢迎点赞 转发。
