[algorithm] 각 정렬 알고리즘은 언제 사용됩니까? [닫은]

첫째, 정의는 매우 중요하기 때문에 정의입니다. 안정적인 정렬 은 동일한 키로 요소를 재정렬하지 않도록 보장하는 것입니다.

추천 :

빠른 정렬 : 안정적인 정렬이 필요하지 않고 평균 사례 성능이 최악의 경우보다 중요합니다. 빠른 정렬은 평균 O (N log N), 최악의 경우 O (N ^ 2)입니다. 좋은 구현은 재귀를 위해 스택 공간 형태로 O (log N) 보조 기억 장치를 사용합니다.

정렬 정렬 : 안정적인 O (N log N) 정렬이 필요한 경우 이것이 유일한 옵션입니다. 그것의 유일한 단점은 O (N) 보조 공간을 사용하고 빠른 정렬보다 약간 큰 상수를 가지고 있다는 것입니다. 적절한 병합 정렬이 있지만 AFAIK는 모두 O (N log N)보다 안정적이거나 나쁘지 않습니다. 제자리에있는 O (N log N)조차도 평범한 기존 병합 정렬보다 상수가 훨씬 커서 유용한 알고리즘보다 이론적 호기심이 많습니다.

힙 정렬 : 안정적인 정렬이 필요하지 않고 평균 케이스 성능보다 최악의 케이스 성능에 더 관심이있는 경우. O (N log N)이어야하며 O (1) 보조 공간을 사용하므로 매우 큰 입력에서 예기치 않게 힙 또는 스택 공간이 부족하지 않습니다.

Introsort : 빠른 정렬의 O (N ^ 2) 최악의 경우를 피하기 위해 특정 재귀 깊이 후에 힙 정렬로 전환되는 빠른 정렬입니다. O (N log N) 성능을 보장하면서 빠른 정렬의 평균 사례를 얻으므로 거의 항상 일반 오래된 빠른 정렬보다 낫습니다. 아마도 이것 대신 힙 정렬을 사용하는 유일한 이유는 O (log N) 스택 공간이 실질적으로 중요한 메모리 제한 시스템에 있기 때문입니다.

삽입 정렬 : 빠른 정렬 또는 병합 정렬의 기본 사례를 포함하여 N이 작을 때. 이것은 O (N ^ 2)이지만 상수는 매우 작으며 안정적인 정렬입니다.

Bubble sort, selection sort : 빠르고 더러운 일을 할 때 어떤 이유로 든 표준 라이브러리의 정렬 알고리즘을 사용할 수 없습니다. 삽입 정렬에 비해 이러한 장점은 구현하기가 조금 더 쉽다는 것입니다.

비 비교 정렬 : 상당히 제한된 조건에서는 O (N log N) 장벽을 깨고 O (N)으로 정렬 할 수 있습니다. 시도해 볼 가치가있는 경우는 다음과 같습니다.

계수 정렬 : 범위가 제한된 정수를 정렬 할 때.

기수 정렬 : log (N)이 K보다 상당히 큰 경우 K는 기수의 수입니다.

버킷 정렬 : 입력이 대략 균일하게 분산 될 수 있습니다.

답변

/**
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;