是否可以创建一个通用方法，对数组和链表进行平等排序

Question

我正在做一个任务，需要构建一个通用的Java方法来对链表或数组进行排序，但我不明白这怎么可能。

Answer 1

LinkedList排序实现应该与迭代器一起使用才能高效，因为在没有迭代器的情况下索引和交换元素需要线性时间。因此，LinkedList和数组（或ArrayList）的泛型排序没有多大意义。

例如，如果你想编写一个泛型ArrayList和数组排序，你可以提供两个lambda的实现，用于在某个索引处获取和设置元素：

private static interface Get<E> {
    E get(int index);
}
private static interface Set<E> {
    void set(int index, E e);
}
private static <E extends Comparable<? super E>> void sort(
        Get<E> get, Set<E> set, int size) {
    // ... sorting algorithm
}
public static <E extends Comparable<? super E>> void sort(E[] array) {
    // more verbose syntax if you use Java 7, but it shouldn't affect performance
    sort(i -> array[i], (i, e) -> { array[i] = e; }, array.length);
}
public static <E extends Comparable<? super E>, T extends List<E> & RandomAccess>
sort(T arrayList) {
    sort(arrayList::get, arrayList::set, arrayList.size());
}

我没有测量，但是这种实施不应该比旧的简单方法慢得多（如果有的话），因为 JIT 能够无缝地内联 lambda。