배열과 연결된 목록을 동등하게 정렬하는 일반적인 방법을 만드는 것이 가능합니까?

Question

나는 연결리스트 또는 배열을 정렬하는 일반적인 자바 방법을 구축 필요 할당 작업을하고 있지만 그게 가능할 것이다 방법을 이해하지 않습니다. 반복자없이 인덱싱 및 교환 요소가 선형의 시간이 걸릴 것이기 때문에 반복자와 함께 작동합니다

Answer 1

LinkedList 정렬 구현은 효율적입니다. 따라서 LinkedList 및 배열 (또는 ArrayList)의 일반적인 정렬은별로 의미가 없습니다.

당신은 정렬 일반적인 ArrayList 및 배열을 작성하는 예를 들어, 일부 인덱스에서 요소를 가져오고 설정, 두 개의 람다와 구현을 제공 할 수 싶습니다 :

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()); 
} 

내가 측정하지 않았다 ,이 imlementation은 JIT가 lambda를 완벽하게 인라인 할 수 있기 때문에 이전의 단순한 접근 방식보다 훨씬 느려서는 안됩니다.