Java List Sort

一、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程序員的代碼實現能力以及運行效率。