홈>
중복 데이터로 배열을 배열 할 때 빠른 정렬 속도가 덜 효율적이라고 생각합니까? 데이터 유형이 char이면 배열이 100000 이상 일수록 n ^ 2 순서에 가까워집니다. 중복 데이터가 없다고 가정하면 첫 번째 요소가 피벗으로 배치되는 첫 번째 요소 인 빠른 정렬의 가장 좋은 경우를 얻습니다. 첫 번째 요소 권리? 가장 좋은 경우가 있습니까?
- 답변 # 1
트렌드
- OpenCv의 폴더에서 여러 이미지 읽기 (python)
- 파이썬 셀레늄 모든 "href"속성 가져 오기
- html - 자바 스크립트 - 클릭 후 변경 버튼 텍스트 변경
- javascript - 현재 URL에서 특정 div 만 새로 고침/새로 고침
- JSP에 대한 클래스를 컴파일 할 수 없습니다
- JavaScript 변수를 HTML div에 '출력'하는 방법
- git commit - 자식 - 로컬 커밋 된 파일에 대한 변경을 취소하는 방법
- jquery - JavaScript로 현재 세션 값을 얻으시겠습니까?
- javascript - swiperjs에서 정지, 재생 버튼 추가
- python - 화면에서 찾은 요소를 찾을 수없는 경우 셀레늄
파티션 중 한쪽 끝에서 다른 쪽 끝까지 스캔하는 Lomuto 파티션 구성표는 복제 속도가 느려집니다. 모든 값이 동일하면 각 파티션 단계는 최악의 시나리오 인 1과 n-1 크기로 분할합니다.
인덱스 (또는 이터레이터 또는 포인터)가 교차 할 때까지 양쪽 끝에서 서로를 향해 스캔하는 Hore 파티션 구성표는 일반적으로 복제 속도가 빠릅니다. 중복으로 인해 더 많은 스왑이 발생하더라도 각 스왑은 두 값을 읽은 후 피벗과 비교 한 직후에 발생하며 여전히 스왑 캐시에 있습니다 (객체 크기가 크지 않다고 가정). 복제 수가 증가함에 따라 분할은 각 파티션 단계가 데이터를 두 개의 동일한 반으로 나누는 이상적인 경우를 향해 향상됩니다. 1 천 6 백만 64 비트 정수를 정렬하는 벤치 마크를 실행했습니다. 무작위 데이터의 경우 약 1.37 초가 걸렸으며 중복으로 개선되었으며 모든 값이 동일하면 약 0.288 초가 걸렸습니다.또 다른 대안은 파티션을 요소<피벗, 요소 == 피벗, 요소>피벗으로 분할하는 3 방향 파티션입니다. 모든 요소가 동일하면 O (n) 시간 안에 완료됩니다. k 개의 가능한 값만있는 n 개의 요소의 경우 시간 복잡도는 O (n ⌈log3 (k) ⌉)이고, k가 일정하기 때문에 시간 복잡도는 여전히 O (n)입니다.
위키 링크 :
https://en.wikipedia.org/wiki/Quicksort#Repeated_elements
https://en.wikipedia.org/wiki/Dutch_national_flag_problem