概述
Java 提供了一个丰富的集合框架，包含各种接口和类以满足不同的数据结构需求。然而，它并未内置排序列表的实现。本文将探讨这一缺失的原因，比较插入排序与按需排序的概念，并讨论插入排序可能违反List接口合同的问题，以及如何通过其他方式实现有序行为。
1.1 插入排序与按需排序
理解为何Java中没有内置排序列表的关键在于区分插入排序和按需排序。
1.1.1 插入排序
插入排序在插入元素时立即重新排列，确保每次添加后都有一个排序的顺序。 一些数据结构确实采用这种方式，通常基于树形结构，如TreeSet和TreeMap。
插入排序的主要优点是读取数据的效率，但写入数据成本较高，因为需要找到结构中的合适位置，有时甚至需要调整现有数据。
尽管每次读取时对整个未排序集合进行排序的成本可能较大，但在多条件排序的情况下，插入排序更为复杂，需要维护多个索引树结构，使得保存操作更加复杂且昂贵。
1.1.2 按需排序
另一方面，按需排序将排序操作推迟到用户明确请求时执行。每次读取排序数据时成本较高，因为每次都需要对整个集合进行排序。
优点是保存数据非常简单，底层数据结构可以更简单，例如ArrayList背后的数组。此外，我们可以根据需要在每次排序时选择不同的条件，甚至不进行排序。
2. 为什么插入排序会违反List接口合同
如果使用插入排序，将违反List接口的合同。**List接口的合同规定元素应保持它们被插入的顺序，允许重复元素。** 插入排序通过重新排列元素违反了这一合同，这对于依赖元素顺序的许多列表操作和算法至关重要。
每当我们在列表上进行插入排序时，我们都会改变元素的顺序，可能破坏List接口中定义的其他方法的预期行为。
3. 实现插入排序
在大多数情况下，我们不应自行实现数据结构来实现插入排序。尽管已经有一些实现良好的集合，它们基于树数据结构，而不是线性列表。
3.1 使用默认排序的TreeSet
如果我们满足于自然顺序并忽略重复，可以创建一个带有默认构造函数的TreeSet实例：
TreeSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(5);
sortedSet.add(2);
sortedSet.add(8);
sortedSet.add(1);
System.out.println(sortedSet); // Output: [1, 2, 5, 8]
3.2 使用自定义排序的TreeSet
我们还可以使用自定义的Comparator来实现自定义排序。假设我们有一个字符串集，想要按最后一个字母排序：
Comparator<String> customComparator = Comparator.comparing(str -> str.charAt(str.length() - 1));
TreeSet<String> sortedSet = new TreeSet<>(customComparator);
sortedSet.add("Canada");
sortedSet.add("Germany");
sortedSet.add("Japan");
sortedSet.add("Sweden");
sortedSet.add("India");
System.out.println(sortedSet); // Output: [India, Canada, Sweden, Japan, Germany]
4. 实现按需排序
如果我们想使用List接口，可以实现按需排序。有以下两种方法：就地排序或创建一个新的已排序列表。
4.1 就地排序
要就地排序列表，我们可以使用Collections类的sort方法：它会修改我们的列表，改变元素的顺序：
List<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(2);
numbers.add(8);
numbers.add(1);
System.out.println("Before sorting: " + numbers); // Output: Before sorting: [5, 2, 8, 1]
Collections.sort(numbers);
System.out.println("After sorting: " + numbers); // Output: After sorting: [1, 2, 5, 8]
就地排序通常更快、更节省内存，但本质上它需要在可变集合上工作，这并不总是可取的或可能的。
4.2 不修改原始集合排序
我们也可以不改变原始集合地进行排序。为此，我们将从列表创建一个流，对其进行排序，然后收集到一个新的列表中：
List<Integer> sortedList = numbers.stream().sorted().collect(Collectors.toList());
System.out.println("After sorting: " + sortedList); // Output: After sorting: [1, 2, 5, 8]
System.out.println("Original list: " + numbers); // Output: Original list: [5, 2, 8, 1]
另一种做法是利用前面的知识，不将流元素收集到新列表中，而是收集到TreeSet中。这样，我们就无需显式排序，因为TreeSet的实现会为我们处理。
TreeSet<Integer> sortedSet = numbers.stream().collect(Collectors.toCollection(() -> new TreeSet<>()));
System.out.println("After sorting: " + sortedSet); // Output: After sorting: [1, 2, 5, 8]
System.out.println("Original list: " + numbers); // Output: Original list: [5, 2, 8, 1]
5. 总结
本文分析了Java集合框架中没有内置排序列表实现的深思熟虑的决定，并探讨了如何在需要时利用现有数据结构实现插入排序。最后，我们了解了如何在使用List接口时实现按需排序。