수색…
매개 변수
매개 변수 | 기술 |
---|---|
안정 | 정렬 알고리즘은 정렬 후 동일한 요소의 상대적 순서를 유지하면 안정적 입니다. |
자리에 | 정렬 알고리즘은 O(1) 보조 메모리 (정렬해야하는 배열을 포함하지 않음 O(1) 만 사용하여 정렬하면 현재 위치 에 있습니다. |
최상의 사례 복잡성 | 정렬 알고리즘은 가능한 모든 입력에 대해 실행 시간이 T(n) 이상인 경우 O(T(n)) 의 최상의 사례 시간 복잡성을 갖습니다. |
평균 사례 복잡성 | 정렬 알고리즘은 평균 경우의 시간 복잡도 갖는다 O(T(n)) 의 실행 시간은 가능한 모든 입력들을 통해 평균화 된 경우이며, T(n) . |
최악의 경우의 복잡성 | 정렬 알고리즘은 실행 시간이 최대 T(n) 경우 최악의 경우 O(T(n)) 의 시간 복잡도를 갖습니다. |
정렬의 안정성
정렬의 안정성은 정렬 알고리즘이 결과 출력에서 원래 입력의 등호 키 순서를 유지하는지 여부를 의미합니다.
정렬 알고리즘은 같은 키를 가진 두 객체가 정렬되지 않은 배열에 나타나는 정렬 된 출력에서 같은 순서로 나타나는 경우 안정적이라고합니다.
쌍 목록을 고려하십시오.
(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)
이제 각 쌍의 첫 번째 요소를 사용하여 목록을 정렬합니다.
이 목록을 안정적으로 정렬 하면 아래 목록이 출력됩니다.
(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)
원본 목록에도 (9, 3)
이 (9, 7)
뒤에 나타납니다.
불안정한 정렬 은 아래 목록을 출력합니다 :
(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)
불안정한 정렬은 안정적인 정렬과 동일한 출력을 생성하지만 항상 그런 것은 아닙니다.
잘 알려진 안정된 종류 :
- Merge sort
- 삽입 정렬
- 기수 정렬
- 팀 정렬
- 버블 정렬
잘 알려지지 않은 불안정한 종류 :
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow