一、sort()方法
Java中List接口提供了sort()方法，可以对List集合进行排序，排序方式可以是自然排序，也可以是指定比较器排序。sort()方法实现了基于数组的快速排序算法，由于排序的本质是为了把数据按某种顺序“排列”，因此，List中的元素必须实现Comparable接口，重写该接口的compareTo()方法。若没有实现Comparable接口，则可以使用指定比较器排序。
// 自然排序
List<String> list1 = new ArrayList<>();
list1.add("apple");
list1.add("banana");
list1.add("orange");
Collections.sort(list1);
System.out.println(list1); // [apple, banana, orange]
// 指定比较器排序
List<Person> list2 = new ArrayList<>();
list2.add(new Person("xiaoming", 18));
list2.add(new Person("xiaohong", 20));
list2.add(new Person("xiaogang", 15));
Collections.sort(list2, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
System.out.println(list2); // [Person{name='xiaogang', age=15}, Person{name='xiaoming', age=18}, Person{name='xiaohong', age=20}]
sort()方法的时间复杂度为O(n log(n))，空间复杂度为O(log(n))，其实现方式是快速排序。
二、Collections.sort()方法
Collections类中也提供了sort()方法，与List接口中的sort()方法类似，可以对List集合进行排序，也可以是自然排序，也可以是指定比较器排序。与List接口中的sort()方法不同的是，sort()方法实现方式不同，为归并排序。
// 自然排序
List<String> list1 = new ArrayList<>();
list1.add("apple");
list1.add("banana");
list1.add("orange");
Collections.sort(list1);
System.out.println(list1); // [apple, banana, orange]
// 指定比较器排序
List<Person> list2 = new ArrayList<>();
list2.add(new Person("xiaoming", 18));
list2.add(new Person("xiaohong", 20));
list2.add(new Person("xiaogang", 15));
Collections.sort(list2, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
System.out.println(list2); // [Person{name='xiaogang', age=15}, Person{name='xiaoming', age=18}, Person{name='xiaohong', age=20}]
Collections.sort()方法的时间复杂度为O(n log(n))，空间复杂度为O(n)，其实现方式是归并排序。
三、parallelSort()方法
从JDK 8开始，Java中的List接口提供了parallelSort()方法，该方法与sort()方法类似，可以对List集合进行排序，也可以是自然排序，也可以是指定比较器排序。与前两种方法的不同点是，该方法可以并行进行排序，能够充分利用多核CPU的优势，提升排序的效率。与List接口中的sort()方法类似，parallelSort()方法也要求List中的元素实现了Comparable接口，否则必须使用指定比较器排序。
// 自然排序
List<String> list1 = new ArrayList<>();
list1.add("apple");
list1.add("banana");
list1.add("orange");
Arrays.parallelSort(list1.toArray(new String[0]));
System.out.println(list1); // [apple, banana, orange]
// 指定比较器排序
List<Person> list2 = new ArrayList<>();
list2.add(new Person("xiaoming", 18));
list2.add(new Person("xiaohong", 20));
list2.add(new Person("xiaogang", 15));
Person[] persons = list2.toArray(new Person[0]);
Arrays.parallelSort(persons, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
list2 = Arrays.asList(persons);
System.out.println(list2); // [Person{name='xiaogang', age=15}, Person{name='xiaoming', age=18}, Person{name='xiaohong', age=20}]
parallelSort()方法的时间复杂度与sort()方法类似，为O(n log(n))，空间复杂度为O(log(n))或O(n)，其实现方式跟sort()方法类似，可以是快速排序或归并排序，具体实现取决于参数的大小。
四、实现自定义排序
如果List中的元素没有实现Comparable接口，而且没有指定比较器，无法进行排序。此时，可以通过实现Comparator接口，编写自定义的比较器实现排序。Comparator接口只有一个方法compare()，该方法比较两个对象的大小，返回一个整数，该整数为负数代表第一个参数对象比第二个参数对象小，为0代表两个参数对象相等，为正数代表第一个参数对象比第二个参数对象大。
List<Person> list = new ArrayList<>();
list.add(new Person("xiaoming", 18));
list.add(new Person("xiaohong", 20));
list.add(new Person("xiaogang", 15));
Collections.sort(list, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getName().compareTo(o2.getName());
}
});
System.out.println(list); // [Person{name='xiaogang', age=15}, Person{name='xiaohong', age=20}, Person{name='xiaoming', age=18}]
上述代码通过实现一个比较器，实现了按照人名字母从小到大的顺序排序。
五、总结
Java中List排序有多种方式实现，其中sort()方法和Collections.sort()方法分别使用快速排序和归并排序实现，而parallelSort()方法则可以并行进行快速排序或归并排序。如果List中的元素实现了Comparable接口，则可以使用自然排序；如果List中的元素没有实现Comparable接口，则必须指定比较器来实现排序；如果想要实现自己的排序方式，则需要实现Comparator接口。理解并掌握各种排序方式，能够提高Java程序员的代码实现能力以及运行效率。
