컬렉션이 필요한 이유정렬은 Mergesort를 사용하지만 Arrays를 사용합니다.정렬은 안 되나요?

컬렉션이 필요한 이유정렬은 Mergesort를 사용하지만 Arrays를 사용합니다.정렬은 안 되나요?

JDK-8(x64)을 사용하고 있습니다.위해서Arrays.sort(primitives) Java 문서에서 다음을 발견했습니다.

정렬 알고리즘은 블라디미르 야로슬라브스키, 존 벤틀리, 조슈아 블로흐의 듀얼피봇 퀵소트다.

위해서Collections.sort(객체) "팀소트"를 찾았습니다.

이 실장은 안정적이고 적응성이 높은 반복적인 머지소트입니다.이 구현에서는 지정된 목록을 배열에 덤프하고 배열을 정렬한 후 목록 전체를 반복하여 배열 내의 해당 위치에서 각 요소를 재설정합니다.

한다면Collections.sort어레이를 사용하는데 왜 그냥 호출하지 않는 거죠?Arrays.sort듀얼 피봇 Quick Sort를 사용하시겠습니까?MergeSort를 사용하는 이유

API는 Quicksort가 제공하지 않는 안정적인 정렬을 보장합니다.그러나 원시 값을 자연 순서에 따라 정렬할 때 원시 값에는 식별이 없으므로 차이를 알 수 없습니다.따라서 QuickSort는 원시 어레이에 사용할 수 있으며 보다 효율적이라고 판단될 때 사용됩니다.

오브젝트의 경우, 다른 아이덴티티를 가진 오브젝트가 그 오브젝트에 따라 동등하다고 간주될 때 주의할 수 있습니다.equals실장 또는 제공된Comparator순서를 바꾸다.따라서 QuickSort는 옵션이 아닙니다.따라서 MergeSort의 배리언트가 사용되며 현재 Java 버전에서는 TimSort가 사용됩니다.이것은 두 가지 모두에 해당된다.Arrays.sort그리고.Collections.sortJava 8에서는List정렬 알고리즘을 덮어쓸 수 있습니다.

---

§ QuickSort의 효율의 장점은 인플레이스 시 필요한 메모리가 적다는 것입니다.그러나 TimSort와 같이 어레이에서 사전 정렬된 데이터 실행을 이용할 수 없습니다.

따라서 정렬 알고리즘은 현재 잘못된 이름으로 명명된 클래스에 머무르면서 버전 간에 재작업되었습니다.DualPivotQuicksort또, 설명서는 따라잡지 못했습니다.이것은 일반적으로, 필요 없는 경우에 내부에서 사용되고 있는 알고리즘에 이름을 붙이는 것은 좋지 않은 생각임을 나타내고 있습니다.

현재 상황(Java 8 ~Java 11 포함)은 다음과 같습니다.

• 일반적으로 원시 배열의 정렬 방법에서는 특정 상황에서만 QuickSort를 사용합니다.대규모 어레이의 경우 TimSort와 같이 사전에 정렬된 데이터의 실행을 먼저 식별하고 실행 횟수가 특정 임계값을 초과하지 않을 때 병합합니다.그렇지 않으면 QuickSort로 폴백되지만 작은 범위의 경우 삽입 정렬로 폴백되므로 소규모 어레이뿐만 아니라 빠른 정렬의 재귀에도 영향을 미칩니다.
• sort(char[],…) ★★★★★★★★★★★★★★★★★」sort(short[],…)길이가 특정 임계값을 초과하는 배열에 대해 카운트 정렬을 사용하려면 다른 특수한 경우를 추가합니다.
• 저저마마 likewise likewise likewise likewise likewise likewise likewise likewise.sort(byte[],…)는 카운트 정렬을 사용하지만 임계값은 훨씬 작기 때문에 문서와 가장 대조적입니다.sort(byte[],…)QuickSort를 사용하지 않습니다.소형 어레이의 경우 삽입 정렬만 사용하고 그 이외의 경우에는 카운트 정렬만 사용합니다.

「 」의 , 「 」의 실장은 「 」입니다.java.util.Collections#sortJava 8 (HotSpot) 。

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

★★★★★★★★★★★★★★★★★.List#sort는음

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

'아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 네!Collections#sort는 (오브젝트 요소에 대해) 백그라운드에서 사용합니다.이 구현에서는 병합 정렬 또는 팀 정렬을 사용합니다.

Javadoc에 따르면 QuickSort를 사용하여 기본 배열만 정렬됩니다.오브젝트 배열도 Mergesort를 사용하여 정렬됩니다.

자, 컬렉션.정렬은 배열과 동일한 정렬 알고리즘을 사용하는 것 같습니다.오브젝트를 정렬합니다.

또 다른 질문은 오브젝트 어레이와는 다른 정렬 알고리즘이 원시 어레이에 사용되는 이유입니다.

많은 답변에서 언급되었듯이.

QuickSort는 어레이에서 사용됩니다.안정성이 필요하지 않기 때문에 원시 컬렉션을 정렬하기 위한 정렬(같은 두 개의 int가 정렬되었는지 여부를 알 수 없거나 상관하지 않음)

MergeSort 또는 보다 구체적으로는 TimSort가 어레이에서 사용됩니다.오브젝트 컬렉션을 정렬하기 위한 정렬입니다.안정성이 필요합니다.QuickSort는 안정성을 제공하지 않습니다.Timsort는 안정성을 제공합니다.

컬렉션어레이로 딜러를 정렬합니다.따라서 자바독이 MergeSort를 참조합니다.

Quick Sort에는 병합 정렬에 관한 두 가지 주요 단점이 있습니다.

• 원시적이지 않은 경우에는 안정적이지 않습니다.
• n log n 퍼포먼스를 보증하는 것은 아닙니다.

안정성은 (가치) 평등과 구별되는 정체성의 개념이 없기 때문에 원시 유형에는 문제가 되지 않습니다.

임의의 오브젝트를 정렬할 때는 안정성이 중요합니다.Merge Sort가 입력에 관계없이 n개의 로그 n(시간) 성능을 보증하는 것은 좋은 이점입니다.따라서 객체 참조를 정렬하기 위한 안정적인 정렬(Merge Sort)을 제공하기 위해 병합 정렬이 선택됩니다.

언급URL : https://stackoverflow.com/questions/32334319/why-does-collections-sort-use-mergesort-but-arrays-sort-does-not